Word Pattern

Given a pattern string and a space-separated string s, determine if s follows the same pattern. Each pattern character maps to exactly one word, and no two characters map to the same word.

Why this is worth learning

This is a bijection between pattern bytes and whole tokens. Tokenization is part of the contract, not a harmless implementation detail.

Before coding: one-minute experiment

For pattern "abba", why does "dog dog dog dog" fail?

Function signature

func WordPattern(pattern string, s string) bool

Inputs / outputs

• pattern: pattern of characters.
• s: space-separated words.
• Return: true if the pattern matches, else false.

Example

pattern = "abba", s = "dog cat cat dog"
Output: true

pattern = "abba", s = "dog cat cat fish"
Output: false

Constraints

• 0 <= len(pattern) <= 100_000
• s contains words separated by single spaces.

Core idea (near-solution)

You need a bijection between pattern characters and words. Track both directions:

• char -> word
• word -> char

Invariant: existing mappings must match whenever a character/word repeats.

Algorithm (step-by-step)

1. Split s into words.
2. If counts differ, return false.
3. Iterate over positions:
   • If pattern[i] is mapped, ensure it maps to the current word.
   • If word is mapped, ensure it maps back to pattern[i].
   • Otherwise, record both mappings.
4. Return true.

Correctness sketch

First require one token for every pattern position. During the scan, the character-to-word map prevents a repeated pattern byte from changing its associated word, while the word-to-character map prevents different pattern bytes from sharing a word. A new pair is added only when both existing constraints are satisfied. Induction gives a consistent bijection for all processed positions. After the final position, that bijection explains the entire token sequence, so acceptance is sufficient. Any conflicting pair would violate the definition of a single one-to-one pattern mapping, so rejection is necessary.

Trace (hand walkthrough)

Example input:
pattern = "abba", s = "dog cat cat dog"
Output: true

pattern = "abba", s = "dog cat cat fish"
Output: false

Walk:
- "abba" vs "dog cat cat dog": map a->dog, b->cat; reverse map ok -> true
- "abba" vs "dog cat cat fish": a->dog, b->cat; last word fish != dog -> false

Pitfalls to avoid

• Only mapping one direction.
• Ignoring mismatch in word count.

Debugging lens

Test word-count mismatch and reverse-map collisions independently. The existing implementation uses strings.Split(s," "), not strings.Fields; do not silently change whitespace or empty-token behavior.

Complexity

Expected time: O(len(s)+len(pattern)) including splitting and hashing token bytes. Auxiliary space: O(number of tokens + distinct mappings), with token strings referring to the original text.

Implementation notes (Go)

• Split by spaces and check the word count matches pattern length.
• Maintain two maps to enforce bijection.

Contract precision

The stated ordinary domain uses words separated by single spaces. For compatibility, the supplied splitter also treats empty s as one empty token: WordPattern("", "") is false and WordPattern("a", "") is true. These legacy edge behaviors are retained and reported rather than silently changed.

Reconstruction checkpoint

For pattern "abba", why does "dog dog dog dog" fail?

Return to Hash Map · Module quiz