LeetCode #290 Easy

Word Pattern

Decide whether a string of space-separated words follows a pattern, where each pattern letter must correspond to exactly one word and vice versa.

hash mapstringbijection

Open on LeetCode ↗

02

Intuition

💡

You will build one dictionary, pattern letter to word, check each pair against it, and call it done. Then 'abba' against 'dog dog dog dog' returns True and you will not immediately see why. Your map said a to dog, and when b arrived b was unbound, so you happily added b to dog as well — two different letters now claim the same word, which is not a pattern match, it is a collapse. Follow means bijection, and a bijection has two directions, so you need the reverse map word to letter as well and must reject the moment either side disagrees. There is a second, quieter trap before you even start: zip truncates to the shorter sequence without a word of complaint, so 'ab' against 'dog cat dog' would compare only two pairs, find them consistent, and report True. Compare the lengths first and return False on mismatch. The invariant is that after processing i pairs, the two maps are exact inverses of each other over everything seen so far.

03

Approach

1

Compare lengths before anything else

Split the sentence on spaces and check that the word count equals the pattern length. This guard is not defensive padding — it is load-bearing, because zip silently stops at the shorter input and would let a genuinely mismatched pair through as True. Doing it first also means the loop below never has to worry about running off either sequence.

2

Maintain two maps, checked in both directions

Keep char_to_word and word_to_char. At each position, if the letter is already bound to a different word, fail; if the word is already bound to a different letter, fail. Only the second check catches 'abba' against 'dog dog dog dog', which is why a one-directional solution passes the sample tests and dies on the hidden ones. If neither conflicts, write both entries.

3

Survive the loop, return True

Because every position either agrees with existing bindings or establishes a fresh mutually-exclusive one, reaching the end means the maps are exact inverses across the whole input — that is the bijection the problem asks for. One pass, one comparison per direction, so the whole thing is linear in the total input size.

04

Solution & live demo

python

▶1class Solution:
▶2    def wordPattern(self, pattern: str, s: str) -> bool:
▶3        words = s.split(' ')
▶4        if len(pattern) != len(words):
▶5            return False
▶6        char_to_word = {}
▶7        word_to_char = {}
▶8        for ch, w in zip(pattern, words):
▶9            if char_to_word.get(ch, w) != w:
▶10                return False
▶11            if word_to_char.get(w, ch) != ch:
▶12                return False
▶13            char_to_word[ch] = w
▶14            word_to_char[w] = ch
▶15        return True

05

Edge cases

Length mismatch, 'ab' vs 'dog cat dog'

The up-front length check returns False; without it, zip would truncate to two pairs and wrongly report True.

Two letters claiming one word, 'abba' vs 'dog dog dog dog'

The reverse map already holds dog to a, so binding b to dog is rejected — the case a one-directional map gets wrong.

One letter claiming two words, 'aaaa' vs 'dog cat cat dog'

The forward map holds a to dog and the second word is cat, so it fails on the forward check at index 1.

Repeated word for the same letter, 'abba' vs 'dog cat cat dog'

Both maps already agree at every repeat, so nothing conflicts and the result is True.

06

Complexity

Time

O(n)

Space

O(n)

n is the total length of the input; the maps hold at most one entry per distinct letter and per distinct word.