VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.4 of 12 in this moduleFree

Word Pattern

Does a sentence follow a letter pattern, one word per letter, one-to-one? The same bijection idea as isomorphic strings, with words as keys: from pairwise checks, to two maps, to canonical codes. Then the pitfalls: length mismatches, words sharing a hash bucket, and patterns arriving in a stream.

about 10 min 5 Python examples 2 quick checks

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).

text
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.

python
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".

pattern a b b a against three sentences: dog cat cat dog matches; dog cat cat fish fails because a would map to dog and fish; dog dog dog dog fails because a and b would both map to dog.
Diagram— pattern a b b a against three sentences: dog cat cat dog matches; dog cat cat fish fails because a would map to dog and fish; dog dog dog dog fails because a and b would both map to dog.
python
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

python
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?

  1. Because of the split
  2. Hashing a word reads all of its L characters, so each dict lookup with a new word costs O(L), not O(1)
  3. Because dicts are slow
  4. Because the pattern has 26 letters
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.

python
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.

python
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?

  1. 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
  2. True, because every a maps to dog
  3. An error is raised
  4. True, because dog maps to a
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

  1. Why must the lengths be checked before zipping?
  2. What does each of the two maps catch?
  3. Why isn't a dict lookup O(1) for word keys in the strict sense?
  4. Why does the shape function from 2.3 work unchanged here?
  5. How do you check many lines against one template efficiently?
  6. How does this apply to a merged tokenizer vocabulary?
Answers
  1. zip stops at the shorter input, so extra words or letters would be ignored and give a wrong True.
  2. Letter → word: a letter with two different words. Word → letter: one word used for two letters.
  3. Hashing and comparing a string costs O(length).
  4. It works on any sequence of hashable items: characters, words or ids.
  5. Compute the template's shape once; compare each line's shape: one pass per line.
  6. Check that token → id and id → token are both consistent: a bijection.