Word Pattern: Bidirectional Hash Map Matching

May 15, 20264 min read

leetcodeproblemeasystringshash-map

LeetCode 290, Word Pattern, asks you to determine whether a space-separated string of words follows the same pattern as a given pattern string. Each letter in the pattern maps to exactly one word, and each word maps back to exactly one letter. If you have already worked through Isomorphic Strings, this problem is its close cousin. The twist is that you are mapping characters to full words instead of characters to characters, and the input requires you to split the string first.

pattern = "abba", s = "dog cat cat dog". Each pattern character maps to exactly one word, and each word maps back to exactly one character. The bijection holds, so the answer is true.

Why you need two maps

A single hash map from pattern characters to words is not enough. Consider pattern "abba" and s = "dog dog dog dog". With only one map (char_to_word), you would record a -> "dog" at index 0, then b -> "dog" at index 1. When you reach index 2, b already maps to "dog", which matches. At index 3, a already maps to "dog", which also matches. The single map says everything is fine, but the answer should be false because two different pattern characters (a and b) both point to the same word.

The fix is a second map going the other direction: word_to_char. When you try to assign "dog" to b, the reverse map already shows "dog" -> a. That is a conflict. Two different characters cannot share the same word in a valid bijection. The second map catches it immediately.

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
    char_to_word = {}
    word_to_char = {}
    for c, w in zip(pattern, words):
        if c in char_to_word and char_to_word[c] != w:
            return False
        if w in word_to_char and word_to_char[w] != c:
            return False
        char_to_word[c] = w
        word_to_char[w] = c
    return True

Practice the bijection pattern

Step-by-step walkthrough

Passing example: pattern = "abba", s = "dog cat cat dog"

Step 1: Process index 0. char = 'a', word = "dog". Neither map has these entries.

First pair. 'a' is not in char_to_word, and "dog" is not in word_to_char. Create both mappings: a -> dog and dog -> a.

Step 2: Process index 1. char = 'b', word = "cat". Both are new entries.

Second pair. 'b' is not in char_to_word, and "cat" is not in word_to_char. Add mappings: b -> cat and cat -> b.

Step 3: Process index 2. char = 'b', word = "cat". Check existing mappings.

Third pair. char_to_word['b'] is already "cat", and word_to_char["cat"] is already 'b'. Both match. Consistent.

Step 4: Process index 3. char = 'a', word = "dog". Check existing mappings.

Fourth pair. char_to_word['a'] is already "dog", and word_to_char["dog"] is already 'a'. Both match. Consistent. Return true.

Why bidirectional mapping matters

Failing example: pattern = "abba", s = "dog dog dog dog"

Step 1: Map a -> dog and dog -> a. No conflict yet.

Step 2: char = 'b', word = "dog". Conflict in word_to_char!

'b' is not in char_to_word, so the forward check passes. But word_to_char["dog"] is already 'a', not 'b'. The reverse check fails. Return false. Without the second map, you would miss this.

Drill this pattern with spaced repetition

Complexity analysis

Approach	Time	Space
Two hash maps	O(n)	O(n)

The algorithm iterates through the pattern and word list once. Each lookup and insertion into the hash maps is O(1) on average. The space is O(n) in the worst case when every character and every word is unique. In practice, the character map is bounded by 26 letters, but the word map can grow with the number of distinct words.

The building blocks

Bijective mapping with two hash maps

The core technique here is maintaining a bidirectional mapping. One map alone verifies that each key maps to a consistent value, but it cannot prevent two different keys from mapping to the same value. The second map enforces that constraint. You will see this pattern anywhere a problem asks for a one-to-one correspondence, consistent substitution, or structural equivalence.

The template is always the same:

forward = {}
backward = {}
for a, b in zip(seq1, seq2):
    if a in forward and forward[a] != b:
        return False
    if b in backward and backward[b] != a:
        return False
    forward[a] = b
    backward[b] = a
return True

Pattern matching with zip

The zip function lets you iterate through two sequences in lockstep. In this problem, you zip the pattern string with the list of words. This gives you pairs like ('a', 'dog'), ('b', 'cat'), and so on. Before zipping, you need to check that the two sequences have the same length. If len(pattern) != len(words), there is no valid mapping, and you return False right away.

Edge cases

Length mismatch. If the pattern has 3 characters but the string splits into 4 words, return False immediately. Always check this before entering the loop.
All same characters mapped to the same word. Pattern "aaa" with s = "dog dog dog" is valid. The single mapping a -> "dog" is consistent throughout.
Two different characters mapped to the same word. Pattern "ab" with s = "dog dog" is invalid. a and b are different characters, but both would need to map to "dog". The reverse map catches this.
Single character pattern. Pattern "a" with s = "dog" is valid. There is only one pair to check, and a single mapping is always consistent.

Whenever a problem asks whether two sequences share the same structure or follow a consistent mapping, think "two hash maps." The bijection requirement means you need verification in both directions. One map is never enough on its own.

From understanding to recall

Word Pattern is rated easy, and the code is short. But the two-hash-map technique is the real prize here. It shows up in Isomorphic Strings, encoding validation, and anywhere you need to verify a one-to-one correspondence. Solving it once is good. Solving it from memory three weeks later is better. Spaced repetition helps you internalize the bidirectional check so that when you see "consistent mapping" in a problem statement, the approach is already loaded.

Try CodeBricks free

Isomorphic Strings - Same bijection concept, mapping characters to characters instead of characters to words
Valid Anagram - Character frequency matching with hash maps, checking counts instead of structural mapping
Group Anagrams - Pattern-based grouping where strings sharing the same sorted signature belong together