Word Pattern
EasyPrompt
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:
- Each letter in
patternmaps to exactly one unique word ins. - Each unique word in
smaps to exactly one letter inpattern. - No two letters map to the same word, and no two words map to the same letter.
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 <= 300patterncontains only lower-case English letters.1 <= s.length <= 3000scontains only lowercase English letters and spaces' '.sdoes not contain any leading or trailing spaces.- All the words in
sare separated by a single space.
Approaches
2 approaches with complexity analysis and trade-offs.
We can solve this problem using two HashMaps to maintain the bijection between pattern characters and words in the string.
Algorithm
- Split the input string into words
- Check if pattern length equals words length
- Create two HashMaps:
- One for character to word mapping
- One for word to character mapping
- Iterate through pattern and words simultaneously:
- If character not mapped, check if word is already mapped
- If character is mapped, verify mapping is consistent
- Return true if all mappings are consistent
Walkthrough
This approach uses two HashMaps to track the mapping between pattern characters and words. We first split the string into words and check if the length matches the pattern length. Then, we use one HashMap to store character to word mapping and another for word to character mapping. For each position, we check if the current mappings are consistent.
public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (pattern.length() != words.length) { return false; } Map<Character, String> charToWord = new HashMap<>(); Map<String, Character> wordToChar = new HashMap<>(); for (int i = 0; i < pattern.length(); i++) { char c = pattern.charAt(i); String word = words[i]; if (!charToWord.containsKey(c)) { if (wordToChar.containsKey(word)) { return false; } charToWord.put(c, word); wordToChar.put(word, c); } else { if (!charToWord.get(c).equals(word)) { return false; } } } return true;}Complexity
Time
O(n + k) where n is the length of the pattern and k is the length of the string s (including the split operation)
Space
O(n) where n is the number of unique characters/words
Trade-offs
Pros
Simple and straightforward implementation
Easy to understand and maintain
Good for small to medium sized inputs
Cons
Uses extra space for two HashMaps
Requires splitting the string which takes additional time
Not the most memory-efficient solution
Solutions
Solution
public class Solution { public bool WordPattern ( string pattern , string s ) { var ws = s . Split ( ' ' ); if ( pattern . Length != ws . Length ) { return false ; } var d1 = new Dictionary < char , string >(); var d2 = new Dictionary < string , char >(); for ( int i = 0 ; i < ws . Length ; ++ i ) { var a = pattern [ i ]; var b = ws [ i ]; if ( d1 . ContainsKey ( a ) && d1 [ a ] != b ) { return false ; } if ( d2 . ContainsKey ( b ) && d2 [ b ] != a ) { return false ; } d1 [ a ] = b ; d2 [ b ] = a ; } return true ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.