Problem. Given a pattern of letters and a string s of space-separated words, return True if s follows the
pattern: each letter maps to exactly one word and each word to exactly one letter (a bijection).
pattern = "abba", s = "dog cat cat dog" → True
pattern = "abba", s = "dog cat cat fish" → False
pattern = "abba", s = "dog dog dog dog" → False
pattern = "aaa", s = "dog dog dog dog" → False (lengths differ)
ML context. This is template matching: do these log lines, API paths or prompts follow the same template with consistent slot values? It's also how you check that a vocabulary is a consistent two-way mapping (token ↔ id) after merging two tokenizers.
Lesson 2.3 solved this for characters. Here the "characters" on one side are whole words, which shows the idea generalises to any hashable values.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Separator? | Single spaces | s.split() gives the words |
| Lengths may differ? | Yes | Must return False, not crash |
| Letters? | Lowercase a–z | At most 26 keys on the pattern side |
| Words? | Lowercase, any length | Hashing a word costs O(word length) |
2. Step 2: Brute force: pairwise consistency
Split, check lengths, then for every pair of positions: same letter exactly when same word.
def word_pattern_pairs(pattern, s):
words = s.split()
if len(pattern) != len(words):
return False
n = len(words)
for i in range(n):
for j in range(i + 1, n):
if (pattern[i] == pattern[j]) != (words[i] == words[j]):
return False
return True
assert word_pattern_pairs("abba", "dog cat cat dog")
assert not word_pattern_pairs("abba", "dog cat cat fish")
assert not word_pattern_pairs("abba", "dog dog dog dog")
assert not word_pattern_pairs("aaa", "dog dog dog dog")
print("pairwise check works: O(n² · L) time (L = word length)")
O(n²) pairs, each comparing words of length up to L. Fine for 10 words; slow for a 10⁵-word document checked against a long template.
3. Step 3: Optimise: two maps
First principles (from 2.3): record each letter's word and each word's letter the first time you see them; every later occurrence must agree. The forward map catches "letter with two words"; the reverse map catches "word with two letters".
import random
def word_pattern(pattern, s):
words = s.split()
if len(pattern) != len(words):
return False
letter_to_word, word_to_letter = {}, {}
for ch, w in zip(pattern, words):
if letter_to_word.get(ch, w) != w or word_to_letter.get(w, ch) != ch:
return False
letter_to_word[ch] = w
word_to_letter[w] = ch
return True
def brute(pattern, s):
words = s.split()
return len(pattern) == len(words) and all(
(pattern[i] == pattern[j]) == (words[i] == words[j])
for i in range(len(words)) for j in range(i + 1, len(words)))
rng = random.Random(41)
vocab = ["dog", "cat", "fish"]
for _ in range(2000):
n = rng.randint(0, 6)
pattern = "".join(rng.choice("ab") for _ in range(n))
s = " ".join(rng.choice(vocab) for _ in range(rng.choice([n, n, n + 1])))
assert word_pattern(pattern, s) == brute(pattern, s)
print("two maps: O(n · L) time, matches brute force on 2,000 cases")
- Time: O(total characters): splitting and hashing each word once,
O(n · L). - Space: O(26 + distinct words · L).
Why "O(1)" hides a cost here: a dict lookup hashes the key, and hashing a string of length L is O(L). With characters (2.3) that was constant; with words it isn't. Python caches each string's hash after the first time, so repeated lookups of the same word object are cheap, but the first hash always reads every character.
The same canonical-code shortcut
def shape(seq):
first = {}
return [first.setdefault(x, len(first)) for x in seq]
def word_pattern_canonical(pattern, s):
words = s.split()
return len(pattern) == len(words) and shape(pattern) == shape(words)
assert word_pattern_canonical("abba", "dog cat cat dog")
assert not word_pattern_canonical("abba", "dog dog dog dog")
assert not word_pattern_canonical("aaa", "dog dog dog dog")
print("the shape function from 2.3 works unchanged on words")
shape doesn't care whether its items are characters, words or cluster ids: anything hashable works. That's the
payoff of solving the general problem once.
Quick check
Why is the two-map solution O(n · L) rather than O(n) when the values are words?
Show the answer
B. Hashing a word reads all of its L characters, so each dict lookup with a new word costs O(L), not O(1) — 'O(1) lookup' assumes constant-size keys; string keys cost time proportional to their length to hash and compare.
4. When the constraints change
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| Classic | Two maps (or shape codes) | O(n · L) | O(distinct words · L) |
| Words separated by any whitespace / punctuation | Tokenise first (regex), then the same check | O(total chars) | same |
Pattern without spaces: "does s split into words that follow the pattern?" |
Backtracking search (module 10) | exponential worst case | O(n) |
| Many sentences, one pattern | Precompute the pattern's shape once, compare each sentence | O(n · L) each | O(n) |
| Group sentences by template | Shape code as a dict key | O(total length) | O(total length) |
| Very long words, memory tight | Map each word to an integer id first (interning), then compare ids | O(total chars) | O(vocabulary) |
Change A: match many log lines against one template
Compute the template's shape once; each line then costs one split and one shape.
def shape(seq):
first = {}
return tuple(first.setdefault(x, len(first)) for x in seq)
template = "user X logged in from Y as X".split()
target = shape(template)
lines = [
"user alice logged in from paris as alice",
"user bob logged in from rome as carol",
"user eve logged in from oslo as eve",
]
matches = [line for line in lines if shape(line.split()) == target]
assert matches == [lines[0], lines[2]]
print("lines following the template:", len(matches))
The shape treats the fixed words ("user", "logged") as slots too; in practice you'd mark which positions are constants and require exact matches there, and slots elsewhere. The bijection check is the core either way.
Change B: a two-way vocabulary check
After merging tokenizers, every token must have exactly one id and every id exactly one token. That's this
problem on the (token, id) pairs.
def is_bijection(pairs):
fwd, rev = {}, {}
for a, b in pairs:
if fwd.setdefault(a, b) != b or rev.setdefault(b, a) != a:
return False
return True
assert is_bijection([("the", 0), ("cat", 1), ("the", 0)])
assert not is_bijection([("the", 0), ("cat", 0)]) # two tokens share id 0
assert not is_bijection([("the", 0), ("the", 1)]) # one token, two ids
print("vocabulary is checked in both directions")
Quick check
pattern = 'aaa', s = 'dog dog dog dog'. What should happen and why?
Show the answer
A. False: there are 3 letters and 4 words, so they can't correspond one-to-one; check the lengths before zipping, since zip silently drops the extra word — zip stops at the shorter input, so without the length check the extra word would be ignored and the answer would be wrong.
5. Saying it out loud
"Split into words and check the counts match first, because zip would silently drop extras. Then it's the isomorphism check with words as values: a letter-to-word map and a word-to-letter map, each new pair must agree with both. O(n · L), since hashing a word reads its characters. Equivalently, compare first-occurrence shape codes, which also lets me group many sentences by template."
Check yourself
- Why must the lengths be checked before zipping?
- What does each of the two maps catch?
- Why isn't a dict lookup O(1) for word keys in the strict sense?
- Why does the
shapefunction from 2.3 work unchanged here? - How do you check many lines against one template efficiently?
- How does this apply to a merged tokenizer vocabulary?
Answers
zipstops at the shorter input, so extra words or letters would be ignored and give a wrongTrue.- Letter → word: a letter with two different words. Word → letter: one word used for two letters.
- Hashing and comparing a string costs O(length).
- It works on any sequence of hashable items: characters, words or ids.
- Compute the template's shape once; compare each line's shape: one pass per line.
- Check that token → id and id → token are both consistent: a bijection.