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: Given a pattern string and a sentence, determine whether the words in the sentence follow the same pattern. Each character in pattern must map to exactly one word, and no two characters can map to the same word.
Approach 1: Hash Map Mapping (O(n) time, O(n) space)
Split the input sentence into words and iterate through them alongside the pattern characters. Use a hash map to store the mapping from pattern character to word. When you encounter a character, check whether it already has a mapped word. If it does, verify the current word matches that mapping. If it does not, ensure the word is not already mapped to another character by tracking used words with a set or reverse map. Hash lookups keep each check constant time, giving O(n) time where n is the number of words, and O(n) space for the mappings. This approach relies on a classic hash table for fast lookups and works well for general pattern-to-token matching problems.
Approach 2: Index Mapping (O(n) time, O(n) space)
Instead of storing explicit mappings, track the last seen index of each pattern character and each word. Use two hash maps: one for characters and one for words. While iterating, compare the last seen indices for the current character and word. If they differ, the pattern breaks because the two elements were previously associated with different positions. Update both maps with the current index after each step. This technique ensures that characters and words share identical occurrence patterns. The iteration runs once over the tokens, so the complexity is O(n) time and O(n) space. The logic is concise and avoids explicit bijection checks while still leveraging hash tables and simple string operations.
Recommended for interviews: The hash map mapping approach is the most intuitive and commonly expected in interviews. It directly models the bijection between characters and words and clearly demonstrates your understanding of hash-based lookups. The index mapping trick is slightly more elegant and reduces explicit checks, which can impress interviewers once the basic solution is understood.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 you need an explicit bijection between pattern characters and words |
| Index Mapping | O(n) | O(n) | When you want a concise implementation that checks pattern consistency via last seen indices |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,123 views views
Watch 9 more video solutions →Practice Word Pattern with our built-in code editor and test cases.
Practice on FleetCode