Problem Statement

Word Pattern

You get a short pattern of letters like "abba", and a sentence of words like "dog cat cat dog". The question is: do the words follow the same shape as the letters? In "abba" the first and last letters are the same, and the two middle letters are the same. So the words have to match that, the first and last word the same, and the two middle words the same. There is one more rule. The matching has to be a bijection. A bijection means a strict one-to-one pairing, each letter sticks to exactly one word, and each word sticks to exactly one letter, with no two letters allowed to share the same word. So we keep two lookup tables (called maps), one going each direction, to make sure the pairing stays clean both ways. A map is just a labeled box, you put in a key (like the letter 'a') and it remembers the value (like the word "dog"), so you can ask it later "what did 'a' point to?". This is the same idea as the Isomorphic Strings problem, except here we pair letters with whole words instead of with single characters.

easyHash TableArrays & HashingTime: O(n) · Space: O(n)

Signals to notice

check if string follows word-to-pattern mappingbijection between words and pattern charssame as isomorphic strings

Brute force first

Try all mappings — O(n!).

The key insight

Two maps: pattern char → word AND word → pattern char. Check consistency at each position. O(n × m) where m is average word length.

Trace it on `pattern="abba", s="dog cat cat dog"`

words=[dog,cat,cat,dog], len 4 == len(pattern) 4 -> continue; maps empty
i=0 (a,dog): a unseen, dog unseen -> charToWord={a:dog}, wordToChar={dog:a}
i=1 (b,cat): b unseen, cat unseen -> charToWord={a:dog,b:cat}, wordToChar={dog:a,cat:b}
i=2 (b,cat): charToWord[b]=cat==cat ok, wordToChar[cat]=b==b ok -> no change
i=3 (a,dog): charToWord[a]=dog==dog ok, wordToChar[dog]=a==a ok -> no change
loop ends, all consistent -> return true

What must stay true

Same as isomorphic strings but with characters and words. The mapping must be bijective — each pattern char maps to exactly one word and vice versa.

Shape of the loop

words = split(s)
if len(pattern) != len(words): return false
charToWord = {}, wordToChar = {}
for (ch, word) in zip(pattern, words):
    if (ch in charToWord and charToWord[ch] != word): return false
    if (word in wordToChar and wordToChar[word] != ch): return false
    charToWord[ch] = word; wordToChar[word] = ch
return true

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only checking one direction — 'a b' matching 'cc cc' requires both directions to detect the inconsistency.

Arrays & Hashing Pattern