Word Pattern LeetCode Solution: Bijection Mapping Walkthrough

LeetCode 290, Word Pattern, asks a deceptively simple question: does a string of space-separated words follow the same structure as a given pattern of characters? On the surface it looks like basic string comparison, but the real challenge is enforcing a strict one-to-one mapping in both directions.

If you have already solved Isomorphic Strings (#205), you will recognize the technique instantly. The only difference is that word pattern maps characters to entire words instead of characters to characters. The underlying algorithm — bidirectional hash map validation — is identical.

This problem is a favorite in coding interviews because it tests whether you understand structural equivalence. It is not enough to check that each pattern character maps to a word; you must also verify that each word maps back to exactly one character. Miss that second check and half the test cases will fail.

You are given a pattern string like "abba" and a sentence string like "dog cat cat dog". The question is whether there exists a bijection — a one-to-one and onto mapping — between each character in the pattern and each word in the sentence, such that replacing every character with its mapped word reproduces the sentence exactly.

For pattern "abba" and s "dog cat cat dog", the answer is true. Character a maps to "dog" and character b maps to "cat". Applying the mapping to "abba" yields "dog cat cat dog", which matches.

For pattern "abba" and s "dog cat cat fish", the answer is false. Character a maps to "dog" on the first occurrence, but the fourth position requires a to map to "fish" — a conflict.

For pattern "aaaa" and s "dog cat cat dog", the answer is also false. Character a maps to "dog" first, but the second position has "cat", which breaks the mapping immediately.

The critical insight is that a single map from characters to words is not sufficient. Consider pattern "abba" with s "dog dog dog dog". A char-to-word map would assign a to "dog" and b to "dog", and every lookup would succeed. But this is wrong — two different pattern characters are mapping to the same word, which violates the bijection requirement.

To catch this, you need two maps: one from characters to words (charToWord) and one from words to characters (wordToChar). Every time you process a pair, you check both maps. If charToWord already has the character mapped to a different word, return false. If wordToChar already has the word mapped to a different character, return false. Only if both maps are consistent — or the entries are new — do you proceed.

This two-map technique guarantees a true bijection. It is the same approach used in Isomorphic Strings, and once you internalize it, you can apply it to any structural equivalence problem.

Start by splitting the sentence string on spaces to get an array of words. Immediately check whether the length of this array equals the length of the pattern string. If they differ, the mapping is impossible — return false right away.

Initialize two hash maps: charToWord and wordToChar. Iterate through the pattern and words arrays simultaneously. At each index, look up the current character in charToWord and the current word in wordToChar.

If the character already maps to a different word, or the word already maps to a different character, return false. Otherwise, add both mappings and continue. If the loop completes without conflict, return true.

The time complexity is O(n) where n is the number of words, since you visit each pair exactly once. The space complexity is O(n) for the two hash maps. This is optimal — you cannot solve the problem without examining every character-word pair at least once.

Walking through concrete examples cements the algorithm. Let us trace three cases that cover the main scenarios: a true result, a char-to-word conflict, and a word-to-char conflict.

Example 1: pattern "abba", s "dog cat cat dog". Index 0: a maps to "dog", "dog" maps to a — both new, add them. Index 1: b maps to "cat", "cat" maps to b — both new, add them. Index 2: b is already mapped to "cat" and the current word is "cat" — consistent. "cat" is already mapped to b — consistent. Index 3: a is already mapped to "dog" and the current word is "dog" — consistent. "dog" is already mapped to a — consistent. All pairs check out, return true.

Example 2: pattern "abba", s "dog cat cat fish". Indices 0 through 2 proceed exactly as above. Index 3: a is already mapped to "dog" but the current word is "fish" — conflict in charToWord. Return false immediately.

Example 3: pattern "aaaa", s "dog cat cat dog". Index 0: a maps to "dog", "dog" maps to a — both new. Index 1: a is already mapped to "dog" but the current word is "cat" — conflict in charToWord. Return false immediately. This case fails on the very second pair.

The most common edge case is a length mismatch between the pattern and the word array. Pattern "abc" with s "dog cat" has three characters but only two words — return false before doing any mapping work.

A single-character pattern with a single word is always true, since the trivial mapping cannot conflict with anything. Pattern "a" and s "dog" returns true.

When all pattern characters are the same, like "aaa", the sentence must also consist of the same word repeated. "dog dog dog" returns true, but "dog dog cat" returns false because a would need to map to both "dog" and "cat".

Empty inputs depend on the problem constraints. LeetCode guarantees non-empty pattern and non-empty s, but in a real interview it is worth confirming this with your interviewer before assuming.

Word Pattern drills a fundamental concept in algorithm design: structural equivalence through bidirectional mapping. Any time a problem asks whether two sequences share the same structure — same repetition pattern, same grouping logic, same relational shape — the two-map approach is your go-to tool.

This technique appears in Isomorphic Strings (#205), Word Pattern (#290), and variations like Word Pattern II (#291, which uses backtracking). Mastering the bijection check here gives you a reusable template for an entire family of problems.

The broader lesson is that many LeetCode problems are not unique — they are the same core idea wearing different costumes. Recognizing the shared pattern across problems is far more valuable than memorizing individual solutions. YeetCode flashcards are designed to reinforce exactly this kind of pattern recognition, helping you recall the bidirectional mapping template when you see a new problem that fits the mold.