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
We can optimize the space usage by using a single HashMap and storing the first occurrence index of both pattern characters and words.
Algorithm
- Split the input string into words
- Check if pattern length equals words length
- Create a single HashMap to store indices
- Iterate through pattern and words:
- Store and compare first occurrence indices
- If indices don't match, return false
- Return true if all indices match
Walkthrough
This approach uses a single HashMap to store the first occurrence indices. We can compare the indices of pattern characters and words to determine if they follow the same pattern. This eliminates the need for two separate mappings.
public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (pattern.length() != words.length) { return false; } Map<Object, Integer> map = new HashMap<>(); for (int i = 0; i < words.length; i++) { // Use Integer.valueOf(pattern.charAt(i)) to store char as Object // and words[i] as Object in the same map if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) { 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, but with a smaller constant factor than the two HashMaps approach
Trade-offs
Pros
Uses less space compared to two HashMaps approach
More elegant solution
Handles both character and word mappings in a single data structure
Cons
Slightly less intuitive than the two HashMaps approach
Still requires splitting the string
May be harder to modify for different requirements
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 ; } }class Solution { public boolean wordPattern ( String pattern , String s ) { String [] ws = s . split ( " " ); if ( pattern . length () != ws . length ) { return false ; } Map < Character , String > d1 = new HashMap <>(); Map < String , Character > d2 = new HashMap <>(); for ( int i = 0 ; i < ws . length ; ++ i ) { char a = pattern . charAt ( i ); String b = ws [ i ]; if (! d1 . getOrDefault ( a , b ). equals ( b ) || d2 . getOrDefault ( b , a ) != a ) { return false ; } d1 . put ( a , b ); d2 . put ( b , a ); } return true ; } }class Solution { public: bool wordPattern ( string pattern , string s ) { istringstream is ( s ); vector < string > ws ; while ( is >> s ) { ws . push_back ( s ); } if ( pattern . size () != ws . size ()) { return false ; } unordered_map < char , string > d1 ; unordered_map < string , char > d2 ; for ( int i = 0 ; i < ws . size (); ++ i ) { char a = pattern [ i ]; string b = ws [ i ]; if (( d1 . count ( a ) && d1 [ a ] != b ) || ( d2 . count ( b ) && d2 [ b ] != a )) { return false ; } d1 [ a ] = b ; d2 [ b ] = a ; } return true ; } };''' >>> p = "abba" >>> s = "dog cat cat dog".split() >>> s ['dog', 'cat', 'cat', 'dog'] >>> zip(p,s) [('a', 'dog'), ('b', 'cat'), ('b', 'cat'), ('a', 'dog')] >>> set(zip(p,s)) set([('b', 'cat'), ('a', 'dog')]) >>> >>> >>> s = "dog dog dog dog".split() # then false for: len(set(pattern)) == len(set(str)) >>> zip(p,s) [('a', 'dog'), ('b', 'dog'), ('b', 'dog'), ('a', 'dog')] >>> set(zip(p,s)) set([('a', 'dog'), ('b', 'dog')]) ''' class Solution ( object ): def wordPattern ( self , pattern , s ): """ :type pattern: str :type s: str :rtype: bool """ s = s . split () a = zip ( pattern , s ) return len ( pattern ) == len ( s ) and len ( set ( a )) == len ( set ( pattern )) == len ( set ( s )) ############ class Solution : def wordPattern ( self , pattern : str , s : str ) -> bool : s = s . split ( ' ' ) n = len ( pattern ) if n != len ( s ): return False c2str , str2c = defaultdict (), defaultdict () for i in range ( n ): k , v = pattern [ i ], s [ i ] if k in c2str and c2str [ k ] != v : return False if v in str2c and str2c [ v ] != k : return False c2str [ k ], str2c [ v ] = v , k return TrueVideo 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.