Match words against a letter pattern

What "matches" means. A word matches the pattern when the two strings have the same length and there is a bijection between their letters: the same pattern letter always lines up with the same word letter, and two different pattern letters never line up with the same word letter. Checking only one direction is the classic bug. With pattern ab and word zz, the map a→z, b→z is consistent but not one-to-one, so zz must be rejected.

Brute force. For each word, walk both strings once with two dictionaries, p→w and w→p. On every position, if either dictionary already holds a different partner, the word fails. This is O(L) per word and is already optimal for a single word. State it first; many interviewers accept it as the answer to part 1.

Normalized signature. A cleaner way to see the bijection: replace every letter by the index of its first appearance in that string. abba becomes (0, 1, 1, 0), xyyx becomes (0, 1, 1, 0), and xxxx becomes (0, 0, 0, 0). Two strings are related by a bijection exactly when their signatures are equal. The signature captures "which positions hold equal letters", and a bijection preserves that in both directions. Compute the pattern's signature once, then compare each word's signature against it. This also lets you group many words by shape with a hash map, which is the natural follow-up.

Invariants. While scanning, the two maps are always inverses of each other on the letters seen so far. A word is accepted only if the scan finishes with that still true and the lengths are equal.

from collections import defaultdict


def matches(pattern: str, word: str) -> bool:
    """Two-map check: O(L) time, O(alphabet) space."""
    if len(pattern) != len(word):
        return False
    p_to_w: dict[str, str] = {}
    w_to_p: dict[str, str] = {}
    for p, w in zip(pattern, word):
        if p_to_w.setdefault(p, w) != w:
            return False
        if w_to_p.setdefault(w, p) != p:
            return False
    return True


def signature(s: str) -> tuple[int, ...]:
    """Each character replaced by the index of its first occurrence."""
    first: dict[str, int] = {}
    return tuple(first.setdefault(ch, len(first)) for ch in s)


def match_words(pattern: str, words: list[str]) -> list[bool]:
    """For each word, whether it follows the pattern."""
    target = signature(pattern)
    return [len(w) == len(pattern) and signature(w) == target for w in words]


def group_by_shape(words: list[str]) -> list[list[str]]:
    """Follow-up: bucket words that share a pattern with each other."""
    groups: dict[tuple[int, ...], list[str]] = defaultdict(list)
    for w in words:
        groups[signature(w)].append(w)
    return list(groups.values())


def matches_tokens(pattern: str, sentence: str) -> bool:
    """Follow-up (LC 290 shape): each pattern letter maps to a whole word."""
    tokens = sentence.split()
    if len(tokens) != len(pattern):
        return False
    first_p: dict[str, int] = {}
    first_t: dict[str, int] = {}
    return all(
        first_p.setdefault(p, i) == first_t.setdefault(t, i)
        for i, (p, t) in enumerate(zip(pattern, tokens))
    )


if __name__ == "__main__":
    assert match_words("abba", ["xyyx", "xxxx", "qrrq", "xyzx", "xyy"]) == [
        True, False, True, False, False]
    assert matches("ab", "zz") is False
    assert matches("aa", "zy") is False
    assert matches("", "") is True
    assert match_words("abc", ["cab", "dee", "xyz"]) == [True, False, True]
    assert all(matches("abba", w) == r
               for w, r in zip(["xyyx", "xxxx"], match_words("abba", ["xyyx", "xxxx"])))
    assert sorted(map(sorted, group_by_shape(["moon", "soon", "deed", "abba", "see"]))) == [
        ["abba", "deed"], ["moon", "soon"], ["see"]]
    assert matches_tokens("abba", "red blue blue red") is True
    assert matches_tokens("abba", "red red red red") is False
    print("ok")

• signature(s): O(L) time, O(min(L, alphabet)) space.
• match_words: O(P + Σ|w|) time over all words, since each word is scanned once and words of the wrong length are rejected in O(1). Extra space is O(L) for one signature at a time plus O(n) for the result.
• matches (two maps): O(L) time, O(alphabet) space; it stops at the first conflict.
• group_by_shape: O(Σ|w|) time and space for the keys.

• pattern="abba", words=["xyyx","xxxx","qrrq","xyzx","xyy"] → [True, False, True, False, False].
• pattern="ab", word="zz" → False (forward map is fine, reverse map breaks).
• pattern="aa", word="zy" → False (forward map breaks).
• pattern="abc", words=["cab","dee","xyz"] → [True, False, True].
• Length mismatch: pattern="abba", word="xyy" → False.
• Empty pattern and empty word → True; empty word list → [].
• Pattern equal to the word, e.g. "hello" vs "hello" → True.
• Single letter pattern "a" against any one-letter word → True.

• Words instead of letters (LeetCode 290 shape). Each pattern letter maps to a whole space-separated word. Split the sentence into tokens and run the same bijection check on tokens; matches_tokens does this with first-index signatures.
• Group a dictionary by shape / answer many patterns. Precompute signature(word) for the whole dictionary into a hash map from signature to words. Each pattern query is then one O(P) signature plus a lookup, instead of a scan of every word.
• Pattern letters map to substrings of unknown length (Word Pattern II, LeetCode 291). There are no separators, so you backtrack: for each pattern letter, either use its existing mapping (must be a prefix of the rest) or try every unused substring. Keep both maps for the bijection and prune when the remaining string is shorter than the remaining pattern. This is exponential in the worst case; say so and mention pruning by minimum lengths.
• Wildcards in the pattern (e.g. ? matches any single letter and takes part in no mapping). Skip the wildcard positions in the two-map scan; the signature trick no longer applies directly, so fall back to the two maps.
• Streaming or very long words. The two-map scan works one character at a time with O(alphabet) memory and stops on the first conflict, so it handles streams and early rejection; compare it with building a full signature tuple.

Mid-level (L4)

• Gets the length check and the bijection right, including the reverse map (ab vs zz).
• Writes clean code with a working loop over the word list and walks through one example.
• States O(total characters) time.

Senior (L5)

• Explains why a one-directional map is wrong without being prompted and tests that case.
• Offers the normalized signature and uses it to group or index words.
• Handles the LC 290 token version and edge cases (empty input, length mismatch) quickly.

Staff (L6+)

• Frames the problem as comparing equality structure and picks the representation by query shape (one pattern vs many patterns vs many words).
• Sketches the backtracking for Word Pattern II with sound pruning and an honest complexity bound.
• Discusses early exit, memory for long inputs, and Unicode code points versus bytes.