Word Pattern

Difficulty: Easy
Topics: Hash Table, String
Link: https://leetcode.com/problems/word-pattern/

Problem Description

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

Example 1:

Input: pattern = “abba”, s = “dog cat cat dog”

Output: true

Explanation:

The bijection can be established as:

'a' maps to "dog".
'b' maps to "cat".

Example 2:

Input: pattern = “abba”, s = “dog cat cat fish”

Output: false

Example 3:

Input: pattern = “aaaa”, s = “dog cat cat dog”

Output: false

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Solution

1. Problem Deconstruction

Technical Restatement: We must verify whether there exists a bijective mapping between characters in a pattern string and space-delimited words in a string s, where:

Each pattern character maps to exactly one unique word
Each word maps to exactly one unique pattern character
The mapping preserves order correspondence between pattern indices and word indices
All words must be non-empty

Beginner-Friendly Version: Imagine you have a secret code (the pattern) where each letter stands for a specific word. You’re given a sentence and need to check if:

Each code letter always means the same word throughout
Each word always comes from the same code letter
The order of words matches the order of code letters
No two code letters can share the same word, and no two words can share the same code letter

Mathematical Formulation: Let P = {p₁, p₂, …, pₙ} be the pattern characters Let W = {w₁, w₂, …, wₘ} be the words from s We require:

∃ bijection f: P → W such that ∀i ∈ [1, min(n,m)], f(pᵢ) = wᵢ
f is injective: ∀pᵢ, pⱼ ∈ P, pᵢ ≠ pⱼ ⇒ f(pᵢ) ≠ f(pⱼ)
f is surjective onto the relevant words
n = m (equal lengths)

Constraint Analysis:

1 <= pattern.length <= 300: Allows O(n²) solutions (90,000 operations)
pattern contains only lower-case English letters: 26 possible characters, simplifies character handling
1 <= s.length <= 3000: Maximum 3000 characters, ~1000 words at 3 chars/word
s contains only lowercase English letters and spaces: No special parsing needed
No leading/trailing spaces: Clean input, no trim() required
Single space separation: Simple split() operation suffices
Hidden Edge Cases:
- Pattern and word count mismatch (immediate false)
- Single character pattern with single word
- All identical pattern with varying words
- All varying pattern with identical words
- Mixed patterns with partial matches

2. Intuition Scaffolding

Real-World Metaphor (Language Translation): Think of the pattern as Morse code dots/dashes and words as letters. Each code sequence must decode to exactly one letter, and each letter must encode to exactly one code sequence. If “.-” means “A”, it cannot also mean “B”, and “A” cannot also be represented by “-.”.

Gaming Analogy (Character Classes in RPG): Imagine pattern letters are character classes (Warrior, Mage, Rogue) and words are player names. Each class must have exactly one player, each player must belong to exactly one class, and the party formation order must match the class order.

Math Analogy (Matrix Permutation): Consider pattern as row indices and words as column indices in an adjacency matrix. We need a permutation matrix where exactly one 1 appears in each row and column, preserving the sequence mapping.

Common Pitfalls:

Length Mismatch Oversight: Forgetting to check pattern length vs word count first
One-Way Mapping: Only checking pattern→word direction but not word→pattern
Early Termination: Not handling cases where mapping fails mid-sequence
Case Sensitivity: Problem states lowercase only, but real interviews might test this
Identity Mapping Assumption: Assuming ‘a’ must map to first unique word encountered

3. Approach Encyclopedia

Brute Force Approach:

def wordPattern_brute(pattern, s):
    words = s.split()
    if len(pattern) != len(words):
        return False
    
    n = len(pattern)
    # Check every pair against every other pair
    for i in range(n):
        for j in range(i + 1, n):
            # If same pattern char but different words → violation
            if pattern[i] == pattern[j] and words[i] != words[j]:
                return False
            # If different pattern chars but same word → violation  
            if pattern[i] != pattern[j] and words[i] == words[j]:
                return False
    return True

Complexity Proof:

Time: O(n²) comparisons where n = pattern length
Space: O(n) for storing words list
Mathematical: ∑{i=1}^{n-1} ∑{j=i+1}^{n} 1 = n(n-1)/2 ∈ Θ(n²)

Visualization:

Pattern: a b b a
Words:  dog cat cat dog

Comparison Matrix:
     dog     cat     cat     dog
a:   [a,dog] [a≠b,dog≠cat] [a≠b,dog≠cat] [a=a,dog=dog] ✓
b:          [b,cat] [b=b,cat=cat] ✓ [b≠a,cat≠dog] ✓
b:                 [b,cat] [b≠a,cat≠dog] ✓
a:                          [a,dog]

Optimized Hash Map Approach:

def wordPattern_optimal(pattern, s):
    words = s.split()
    if len(pattern) != len(words):
        return False
    
    char_to_word = {}
    word_to_char = {}
    
    for char, word in zip(pattern, words):
        # Check pattern → word consistency
        if char in char_to_word:
            if char_to_word[char] != word:
                return False
        else:
            char_to_word[char] = word
            
        # Check word → pattern consistency  
        if word in word_to_char:
            if word_to_char[word] != char:
                return False
        else:
            word_to_char[word] = char
            
    return True

Complexity Proof:

Time: O(n) where n = pattern length (single pass with O(1) dict operations)
Space: O(m + k) where m = unique characters, k = unique words
Mathematical: T(n) = n × (2 × O(1)) = O(n)

Visualization:

Step 0: char_to_word = {}, word_to_char = {}
Step 1: 'a' → 'dog'
        char_to_word = {'a': 'dog'}, word_to_char = {'dog': 'a'}
Step 2: 'b' → 'cat'  
        char_to_word = {'a': 'dog', 'b': 'cat'}, word_to_char = {'dog': 'a', 'cat': 'b'}
Step 3: 'b' → 'cat' ✓ (consistent)
Step 4: 'a' → 'dog' ✓ (consistent)

4. Code Deep Dive

def wordPattern(pattern: str, s: str) -> bool:
    # Split string into words - handles single space separation constraint
    words = s.split()
    
    # Immediate length check - crucial edge case handling
    if len(pattern) != len(words):
        return False
    
    # Dual mapping dictionaries ensure bijection
    char_to_word = {}  # Pattern character → word mapping
    word_to_char = {}  # Word → pattern character mapping
    
    # Iterate through parallel sequences
    for char, word in zip(pattern, words):
        # Check forward mapping consistency
        if char in char_to_word:
            # Existing mapping must match current assignment
            if char_to_word[char] != word:
                return False  # Violation: same char, different word
        else:
            # Create new forward mapping
            char_to_word[char] = word
            
        # Check reverse mapping consistency  
        if word in word_to_char:
            # Existing reverse mapping must match current assignment
            if word_to_char[word] != char:
                return False  # Violation: same word, different char
        else:
            # Create new reverse mapping
            word_to_char[word] = char
            
    # All mappings consistent - bijection verified
    return True

Edge Case Handling:

Example 1 (pattern=“abba”, s=“dog cat cat dog”):
- Line 5: Length check passes (4 == 4)
- Final mappings: {‘a’:‘dog’, ‘b’:‘cat’}, {‘dog’:‘a’, ‘cat’:‘b’} → True
Example 2 (pattern=“abba”, s=“dog cat cat fish”):
- Line 17: ‘a’ already maps to ‘dog’, but encounters ‘fish’ → returns False
Example 3 (pattern=“aaaa”, s=“dog cat cat dog”):
- Line 11: ‘a’ maps to ‘dog’, then encounters ‘cat’ → returns False
Length Mismatch (pattern=“abc”, s=“dog cat”):
- Line 5: Immediate return False

5. Complexity War Room

Hardware-Aware Analysis:

At maximum constraint (n=300), the algorithm uses ~300 iterations
Dictionary operations: O(1) average case, O(n) worst case (collisions rare with 26 chars)
Memory: ~600 entries max (300 char mappings + 300 word mappings)
Estimated memory: 600 × (50 bytes overhead + 10 bytes data) ≈ 36KB (fits in L1 cache)

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(n)	8/10	❌ Fails large N
Single HashMap	O(n)	O(n)	7/10	⚠️ Misses word→char check
Dual HashMap	O(n)	O(n)	9/10	✅ Optimal solution
Array Index	O(n)	O(1)	6/10	⚠️ Limited pattern size

6. Pro Mode Extras

Variants Section:

Word Pattern II (LC 291): Pattern matching with string concatenation

def wordPatternMatch(pattern: str, s: str) -> bool:
    # Backtracking approach needed
    char_to_word = {}
    word_to_char = {}
    
    def backtrack(pattern_idx, s_idx):
        # Complex recursive exploration
        pass

Isomorphic Strings (LC 205): Same concept with single characters

def isIsomorphic(s: str, t: str) -> bool:
    # Identical structure to wordPattern
    return len(s) == len(t) and len(set(zip(s, t))) == len(set(s)) == len(set(t))

Multiple Patterns: Check if string follows any of several patterns

def wordPatternMultiple(patterns: List[str], s: str) -> bool:
    return any(wordPattern(pattern, s) for pattern in patterns)

Interview Cheat Sheet:

First Mention: “This is a bijection verification problem with O(n) time, O(n) space using dual hashmaps”
Key Insight: “We need to check both mapping directions to ensure one-to-one correspondence”
Edge Cases: “Always check length mismatch first - it’s the most common failure”
Optimization Path: “Brute force → single map → dual maps for completeness”
Testing Strategy: “Test with identical patterns, identical words, and mixed cases”

#290 - Word Pattern