Word Pattern

Difficulty: Easy | Acceptance: 44.10% | Paid: No Topics: Hash Table, String

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.

• Examples
• Constraints
• Approach 1: Two Hash Maps
• Approach 2: Hash Map and Set

Examples

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.
s contains only lower-case English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Approach 1: Two Hash Maps

Intuition To establish a bijection (one-to-one mapping) between characters and words, we need to verify two conditions: a character always maps to the same word, and a word is always mapped by the same character. We use two hash maps to store these relationships in both directions.

Steps

• Split the string s into an array of words.
• If the number of words does not match the length of the pattern, return false immediately.
• Initialize two hash maps: one for character-to-word mapping and another for word-to-character mapping.
• Iterate through the pattern and words simultaneously.
• If the character exists in the first map, check if the mapped word matches the current word. If not, return false.
• If the word exists in the second map, check if the mapped character matches the current character. If not, return false.
• If neither exists, create the mapping in both maps.
• If the loop completes without mismatches, return true.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False
        
        char_to_word = {}
        word_to_char = {}
        
        for char, word in zip(pattern, words):
            if char in char_to_word:
                if char_to_word[char] != word:
                    return False
            else:
                char_to_word[char] = word
            
            if word in word_to_char:
                if word_to_char[word] != char:
                    return False
            else:
                word_to_char[word] = char
                
        return True

Complexity

• Time: O(N) where N is the length of the string or pattern. We iterate through the pattern once.
• Space: O(N) to store the hash maps.
• Notes: This approach explicitly checks the bijection property using two maps, making the logic very clear.

Approach 2: Hash Map and Set

Intuition We can optimize space slightly by using only one hash map to store the character-to-word mapping. To ensure the word is not mapped by a different character (bijection), we maintain a set of words that have already been assigned.

Steps

• Split the string s into an array of words.
• If the number of words does not match the length of the pattern, return false.
• Initialize a hash map for character-to-word mapping and a set to store used words.
• Iterate through the pattern and words.
• If the character is already in the map, verify that the mapped word matches the current word.
• If the character is not in the map, check if the current word is already in the set of used words. If it is, return false because another character already maps to it.
• Otherwise, add the mapping to the map and add the word to the set.
• Return true if the loop finishes.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False
        
        char_to_word = {}
        used_words = set()
        
        for char, word in zip(pattern, words):
            if char in char_to_word:
                if char_to_word[char] != word:
                    return False
            else:
                if word in used_words:
                    return False
                char_to_word[char] = word
                used_words.add(word)
                
        return True

Complexity

• Time: O(N) where N is the length of the string or pattern.
• Space: O(N) to store the map and the set.
• Notes: This approach is functionally similar to the two-map approach but uses a set to check for value collisions, which can be slightly more intuitive for some.