Word Pattern
Check whether a string of words follows a letter pattern with two hash maps, letter to word and word to letter, after checking the counts match.
Problem Understanding
Word Pattern: given a pattern of letters and a string s of space-separated words, decide whether s follows the pattern. Each letter must map to exactly one word and each word to exactly one letter, a bijection.
Example: pattern = "abba", s = "dog cat cat dog" returns true; with s = "dog cat cat fish" it returns false.
The Intuition: Isomorphic Strings With Words
This is Isomorphic Strings where one side is words instead of letters. Split s into words and pair pattern[i] with words[i].
- Different counts: return
falsestraight away. - Letter → word map: a letter that already means another word is a clash.
- Word → letter map: a word that already belongs to another letter is a clash.
- Otherwise record the pair in both hash maps.
Both directions matter: "ab" and "dog dog" pass the first map but fail the second.
Interactive Walkthrough
Each column stacks a pattern letter over its word; both maps are beside the figure. Try Word reused to see a clash only the word → letter map catches.
Dry Run Table
Input: pattern = "abba", s = "dog cat cat fish"
| Pair | Letter map | Word map | Result |
|---|---|---|---|
| a, dog | new | new | record |
| b, cat | new | new | record |
| b, cat | b → cat ✓ | cat → b ✓ | ok |
| a, fish | a → dog ✗ | — | clash |
Answer: false.
The Solution Template
Split, compare counts, then two maps. C has no hash map, so it compares every pair of positions instead: two positions must have equal letters exactly when they have equal words (O(n²), fine for LeetCode's limits).
Word Pattern Code
1var wordPattern = function(pattern, s) {2 const words = s.split(' ');3 if (words.length !== pattern.length) return false;4 const pToW = new Map(), wToP = new Map();5 for (let i = 0; i < words.length; i++) {6 const p = pattern[i], w = words[i];7 if ((pToW.has(p) && pToW.get(p) !== w) || (wToP.has(w) && wToP.get(w) !== p)) return false;8 pToW.set(p, w);9 wToP.set(w, p);10 }11 return true;12};
Edge Cases & Common Mistakes
- Count mismatch:
"aaa"with"dog dog"must return false before any map lookup. - Only one map:
"ab"/"dog dog"slips past a letter → word map alone. - Java boxing:
wToP.get(w) != pcompares aCharacterwith achar, which unboxes and compares values; comparing twoCharacterobjects with!=would compare references. - Splitting: LeetCode guarantees single spaces and no leading or trailing ones;
split()in Python handles any whitespace anyway.
Summary
Split s into words and return false if the count differs from the pattern length. Then walk letters and words together with two maps, letter → word and word → letter; any disagreement means false. O(n + m) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet