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.The key idea in Word Pattern is to verify whether characters in the pattern map consistently to words in the input string. Each character should correspond to exactly one word, and each word should correspond to only one character. This forms a bijective mapping.
A common strategy is to use a hash table to track relationships between pattern characters and words. As you iterate through the pattern and the list of words simultaneously, ensure that previously seen mappings remain consistent. If a character is already mapped to a word, the current word must match that mapping. Likewise, no two characters should map to the same word.
Another neat trick is storing the last seen indices of characters and words using hash maps to ensure they appear in the same pattern positions.
Since each character-word pair is processed once, the solution runs in O(n) time with O(n) additional space for the hash structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map for Character-Word Mapping | O(n) | O(n) |
| Index Tracking with Hash Maps | O(n) | O(n) |
Ashish Pratap Singh
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.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4#include <stdlib.h>
5#include <ctype.h>
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Word Pattern and similar mapping problems are common in technical interviews at companies like Amazon, Google, and Meta. They test your understanding of hash maps, string processing, and maintaining consistent mappings.
Two mappings help enforce a one-to-one relationship between characters and words. One map tracks character-to-word mapping, while the other ensures that a word is not assigned to multiple characters.
The optimal approach uses hash maps to maintain a consistent mapping between pattern characters and words in the sentence. By checking both directions of the mapping, you ensure a bijection. This allows the problem to be solved in linear time.
Hash tables (hash maps) are the best choice because they allow constant-time lookups for existing mappings. They help track relationships between pattern characters and words efficiently while validating constraints.
In JavaScript, using Map allows for flexible key generation through string concatenation of identifiers (prefix). Identical index retention enforces maintained character-word correspondence and any mismatches diverge immediately.