LeetCode 290: Word Pattern - All Solutions Explained

Problem Statement

The Word Pattern problem (LeetCode 290) is an easy-level hash table challenge where given a pattern and a string s, you need to determine if s follows the same pattern. Here, "follow" means there is a bijection between letters in pattern and non-empty words in s.

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

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

Explanation of the Best Solution

This approach uses two hash maps to track the bidirectional mapping:

1. Check Word Count:
2. Split s into words
3. Verify number of words matches pattern length
4. Create Mappings:
5. char_to_word: pattern char → word
6. word_to_char: word → pattern char
7. Verify Consistency:
8. For each pattern char and word pair:
   • Check if existing mappings match current pair
   • If conflict found, return false
9. Result:
10. Return true if all mappings are consistent

Step-by-Step Example

For pattern = "abba", s = "dog cat cat dog": 1. words = ["dog","cat","cat","dog"] 2. a → dog, dog → a 3. b → cat, cat → b 4. Second b matches existing cat mapping 5. Second a matches existing dog mapping → true

Python Code (Two Maps Solution)

Copy codeclass Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for char, word in zip(pattern, words):
            if char in char_to_word:
                if char_to_word[char] != word:
                    return False
            else:
                if word in word_to_char:
                    return False
                char_to_word[char] = word
                word_to_char[word] = char

        return True

# Test cases
print(Solution().wordPattern("abba", "dog cat cat dog"))  # True
print(Solution().wordPattern("abba", "dog cat cat fish")) # False

Complexity

• Time Complexity: O(n) - Single pass through pattern/words
• Space Complexity: O(m) - Where m is unique chars/words
• Optimizations: Early termination on mismatch

Why It's the Best

• Optimal O(n) time complexity
• Clear bidirectional mapping check
• Handles all edge cases
• Standard approach for pattern matching

Solution 2: Single Index Map (Alternative)

Explanation

This approach maps both pattern chars and words to their first occurrence indices:

1. Check Lengths:
2. Verify pattern and words have same length
3. Create Index Map:
4. Use dictionary to store first occurrence indices
5. Compare Indices:
6. For each char/word pair, check if their indices match
7. Result:
8. Return true if all indices match

Python Code (Index Map Solution)

Copy codeclass Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        index_map = {}

        for i, (char, word) in enumerate(zip(pattern, words)):
            # Use separate keys for pattern chars and words
            char_key = f'char_{char}'
            word_key = f'word_{word}'

            if char_key not in index_map and word_key not in index_map:
                index_map[char_key] = i
                index_map[word_key] = i
            elif char_key not in index_map or word_key not in index_map:
                return False
            elif index_map[char_key] != index_map[word_key]:
                return False

        return True

# Test cases
print(Solution().wordPattern("abba", "dog cat cat dog"))  # True

Complexity

• Time Complexity: O(n) - Single pass
• Space Complexity: O(m) - For index map
• Best for: When you want single map solution

Pros and Cons

• Pros: Single map simplifies implementation
• Cons: Slightly less intuitive than two maps
• Variation: Can use separate maps for chars/words

Solution 3: String Encoding (Clever Approach)

Explanation

This approach encodes both pattern and words as positional sequences:

1. Generate Encodings:
2. For pattern: sequence of first occurrence indices
3. For words: same for word list
4. Compare Encodings:
5. Return true if encodings match
6. Example:
7. "abba" → [0,1,1,0]
8. "dog cat cat dog" → [0,1,1,0]

Python Code (Encoding Solution)

Copy codeclass Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        def encode(sequence):
            encoding = []
            mapping = {}
            for i, item in enumerate(sequence):
                if item not in mapping:
                    mapping[item] = i
                encoding.append(mapping[item])
            return encoding

        return encode(pattern) == encode(words)

# Test cases
print(Solution().wordPattern("abba", "dog cat cat dog"))  # True

Complexity

• Time Complexity: O(n) - Two passes (pattern + words)
• Space Complexity: O(m) - For encoding maps
• When to Use: When you prefer functional approach

Edge Cases to Consider

• Different length pattern and words → false
• All same pattern chars ("aaaa") with matching words
• All same pattern chars with different words → false
• All different pattern chars with same word → false
• Single character/word → true

Final Thoughts

• Two Maps Solution: Best for clarity and efficiency
• Index Map: Good single-map alternative
• Encoding Approach: Clever but less intuitive
• Key Insight: Bijection requires two-way consistency check

For further practice, try similar problems like Isomorphic Strings (LeetCode 205) or Word Pattern II (LeetCode 291).