Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:
pattern maps to exactly one unique word in s.s maps to exactly one letter in pattern.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
The bijection can be established as:
'a' maps to "dog".'b' maps to "cat".Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Constraints:
1 <= pattern.length <= 300pattern contains only lower-case English letters.1 <= s.length <= 3000s contains only lowercase English letters and spaces ' '.s does not contain any leading or trailing spaces.s are separated by a single space.Problem Overview: You are given a pattern string and a space-separated sentence. The task is to determine whether the sentence follows the same pattern. Each character in the pattern must map to exactly one word in the sentence, and no two characters can map to the same word.
This is a classic bijection validation problem. You must ensure a one-to-one relationship between pattern characters and words. Problems like this frequently rely on hash table lookups and efficient string processing.
Approach 1: Hash Map Mapping (O(n) time, O(n) space)
The most direct solution uses two hash maps to enforce a bijection between pattern characters and words. Split the sentence into words, then iterate through both the pattern and word list simultaneously. One map stores char → word and another stores word → char. During iteration, verify that existing mappings remain consistent. If a mismatch appears, return false immediately. Hash lookups make each check constant time, so the overall runtime is O(n) where n is the number of words. This approach is easy to reason about and mirrors how interviewers expect you to validate one-to-one mappings.
Approach 2: Index Mapping (O(n) time, O(n) space)
Instead of storing explicit mappings, track the last index where each pattern character and word appeared. Use two maps: char → last index and word → last index. As you iterate through the sequence, compare the stored indices for the current character and word. If they differ, the pattern relationship is broken. If they match, update both with the current index. This works because valid pairs must always appear at the same positions in their respective sequences. The method still runs in O(n) time with O(n) space but avoids storing full string mappings.
Recommended for interviews: The hash map mapping approach is the most common answer because it clearly demonstrates understanding of bijection constraints. Interviewers expect candidates to enforce both directions of the mapping. The index mapping technique is a clever alternative that reduces conceptual overhead once you recognize the pattern of comparing last-seen indices.
This approach uses two hash maps (dictionaries) to establish bijective mappings between characters in the pattern and words in the string. One map tracks the character to word mapping, while the other tracks word to character mapping. During iteration, we update or check both maps to ensure the bijection property holds.
The solution creates two mappings using arrays, tracking which pattern character maps to each word and vice versa. During each step, the program checks if the current word and character have conflicting existing mappings.
Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in s is checked at least once.
Space Complexity: O(n + m) for storing the mapping of characters to words and words to characters.
The index mapping approach ensures that the last seen indexes of each character in the pattern and each word from s match. By tracking their last occurrences, you can simplify identifying mismatched patterns in linear time.
This C implementation uses two arrays to track the last-occurring index in pattern and s. With words stored in an array, index comparisons determine if the words and pattern characters have been alternating in previously unseen sequences.
Time Complexity: O(n + m), where n is the pattern length and m is s’ length.
Space Complexity: O(n + m) concerning the arrays holding the last occurring indices.
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map Mapping | Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in |
| Approach 2: Index Mapping | Time Complexity: O(n + m), where n is the pattern length and m is s’ length. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Mapping | O(n) | O(n) | General case when validating one-to-one mapping between two sequences |
| Index Mapping | O(n) | O(n) | When you want a concise solution using last-seen index comparisons |
Word Pattern - Leetcode 290 - Python • NeetCode • 50,576 views views
Watch 9 more video solutions →Practice Word Pattern with our built-in code editor and test cases.
Practice on FleetCode