Word Pattern

EASY

Description

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 pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
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 <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Approaches

Checkout 2 different approaches to solve Word Pattern. Click on different approaches to view the approach and algorithm in detail.

Using Two HashMaps

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

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 Analysis

Time Complexity: 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 Complexity: O(n) where n is the number of unique characters/words

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Word Pattern. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Word Pattern

Data Structures:

Hash TableString

Companies:

Dropbox |Google |Zoho |