290. Word Pattern - Explanation

1. Two Hash Maps

Intuition

A valid pattern match requires a bijection (one-to-one correspondence) between pattern characters and words. Each character must map to exactly one word, and each word must map to exactly one character. Using two hash maps allows us to verify both directions of this mapping simultaneously as we iterate through the pattern and words.

Algorithm

Split the string s into an array of words.
If the pattern length does not equal the number of words, return false.
Create two maps: one mapping characters to words, another mapping words to characters.
For each character-word pair, check if existing mappings are consistent with the current pair.
If a conflict is found in either direction, return false. Otherwise, update both mappings.
Return true if all pairs are processed without conflicts.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split(" ")
        if len(pattern) != len(words):
            return False

        charToWord = {}
        wordToChar = {}

        for c, w in zip(pattern, words):
            if c in charToWord and charToWord[c] != w:
                return False
            if w in wordToChar and wordToChar[w] != c:
                return False
            charToWord[c] = w
            wordToChar[w] = c
        return True

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $pattern$ and $m$ is the length of the string $s$ .

2. Two Hash Maps (Optimal)

Intuition

Instead of storing the actual mapping, we store the index where each character or word was last seen. If a character and word form a valid pair, they should always have been last seen at the same index. This elegant approach uses the index as a signature that both the character and word must share to be valid mappings.

Algorithm

Split the string into words and verify the lengths match.
Create two maps storing the last seen index for each character and each word.
For each position, check if the stored index for the current character equals the stored index for the current word.
If they differ, the mapping is invalid; return false.
Update both maps with the current index (using i+1 to distinguish from default 0).
Return true if all positions pass the check.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        charToWord = {}
        wordToChar = {}
        words = s.split()

        if len(pattern) != len(words):
            return False

        for i, (c, word) in enumerate(zip(pattern, words)):
            if charToWord.get(c, 0) != wordToChar.get(word, 0):
                return False
            charToWord[c] = i + 1
            wordToChar[word] = i + 1

        return True

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $pattern$ and $m$ is the length of the string $s$ .

3. Hash Set

Intuition

We can use a hash map to track character to word mappings and a hash set to track which words have already been assigned to some character. When we encounter a new character, we check if its corresponding word is already used by another character. This ensures the bijection property using less memory than two full maps.

Algorithm

Split the string and verify the pattern and word counts match.
Create a map for character to index and a set for used words.
For each character-word pair, if the character was seen before, verify it maps to the same word.
If the character is new, check if the word is already in the used set (which would indicate a duplicate mapping).
If the word is already used by another character, return false. Otherwise, add the mapping and mark the word as used.
Return true if all pairs pass validation.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        charToWord = {}
        store = set()

        for i, (c, w) in enumerate(zip(pattern, words)):
            if c in charToWord:
                if words[charToWord[c]] != w:
                    return False
            else:
                if w in store:
                    return False
                charToWord[c] = i
                store.add(w)

        return True

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $pattern$ and $m$ is the length of the string $s$ .

4. Single Hash Map

Intuition

Using only one hash map from character to index, we can still verify the bijection by iterating through existing mappings when encountering a new character. Since there are at most 26 lowercase letters, this iteration is bounded by a constant. We check if any existing character already maps to the current word, ensuring no two characters share the same word.

Algorithm

Split the string and check that pattern and word counts are equal.
Create a single map from characters to their first occurrence index.
For each character-word pair, if the character exists in the map, verify the stored index points to the same word.
If the character is new, iterate through all existing mappings to ensure no other character maps to this word.
If a conflict is found, return false. Otherwise, add the new mapping.
Return true after processing all pairs successfully.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        charToWord = {}

        for i, (c, w) in enumerate(zip(pattern, words)):
            if c in charToWord:
                if words[charToWord[c]] != w:
                    return False
            else:
                # iterates atmost 26 times (a - z)
                for k in charToWord:
                    if words[charToWord[k]] == w:
                        return False
                charToWord[c] = i

        return True

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $pattern$ and $m$ is the length of the string $s$ .

Common Pitfalls

Only Checking One Direction of the Mapping

A common mistake is using only one hash map to check if each pattern character maps to the same word, but forgetting to verify the reverse. This fails cases like pattern = "abba" and s = "dog dog dog dog" where a -> dog and b -> dog would both be stored, incorrectly returning true.

# Wrong: Only checks character -> word
if c in charToWord and charToWord[c] != w:
    return False
charToWord[c] = w  # Missing reverse check!

Forgetting to Check Length Mismatch Early

Failing to compare the pattern length with the word count before iterating leads to index errors or incorrect results. For example, pattern = "ab" with s = "dog" has a mismatch that should immediately return false.

words = s.split()
# Wrong: Missing this check before the loop
if len(pattern) != len(words):
    return False