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.

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

• Invariant: existing mappings must match whenever a character/word repeats.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

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.

Complexity

• Time: O(n)
• Extra space: O(n) for maps.

Implementation notes (Go)

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