LeetCode 290: Word Pattern Solution in Python – A Step-by-Step Guide

What Is LeetCode 290: Word Pattern?

In LeetCode 290: Word Pattern, you’re given a string pattern (like "abba") and a string s (like "dog cat cat dog"), and your task is to figure out if s follows pattern. “Follows” means each letter in the pattern maps to a unique word in s, and each word maps back to a unique letter—like a perfect two-way match. For example, "abba" matches "dog cat cat dog" because 'a' → "dog," 'b' → "cat," and it works backwards too. But "abba" doesn’t match "dog cat cat fish" because 'a' can’t be both "dog" and "fish." This problem tests your ability to spot mappings, feeling a bit like LeetCode 205: Isomorphic Strings.

Problem Statement

• Input: A string pattern and a string s (space-separated words).
• Output: True if s follows pattern, False otherwise.
• Rules: Each pattern letter maps to one word; each word maps to one letter; lengths must match.

Constraints

• pattern length: 1 to 300.
• s contains 1 to 300 lowercase English words, separated by spaces.
• pattern contains lowercase English letters.

Examples

• Input: pattern = "abba", s = "dog cat cat dog"
• Output: True
• Input: pattern = "abba", s = "dog cat cat fish"
• Output: False
• Input: pattern = "aaaa", s = "dog dog dog dog"
• Output: True
• Input: pattern = "abba", s = "dog dog dog dog"
• Output: False

Understanding the Problem: Matching Letters to Words

To solve LeetCode 290: Word Pattern in Python, we need to check if the words in s line up with the letters in pattern like a perfect dance—each letter gets one word, and each word gets one letter. First, split s into words (e.g., "dog cat cat dog" → ["dog", "cat", "cat", "dog"]). Then, make sure the number of words equals the pattern length, and check that the mappings work both ways. A naive way might be to guess and test, but we’ll use smarter tricks:

• Best Solution (Two-Way Hash Mapping): O(n) time, O(n) space—fast and complete.
• Alternative Solution (Single Hash with List): O(n) time, O(n) space—simpler but less explicit.

Let’s dive into the two-way hash solution with a friendly breakdown that’s easy to follow.

Best Solution: Two-Way Hash Mapping

Why This Is the Best Solution

The two-way hash mapping is the top pick for LeetCode 290 because it’s efficient—O(n) time, where n is the pattern length—and uses O(n) space with two small hash maps. It checks both directions (letter-to-word and word-to-letter) to ensure a perfect match, catching every mismatch in one pass. It’s like having a double-check system that’s quick and reliable—great for this problem!

How It Works

Let’s think of this like pairing friends with nicknames:

• Step 1: Split the Words:
• Take the string s and break it into a list of words—like "dog cat cat dog" becomes ["dog", "cat", "cat", "dog"].
• Step 2: Check Lengths:
• Make sure the pattern length (e.g., 4 for "abba") equals the number of words (4 words). If not, it’s a no-go.
• Step 3: Set Up Two Notebooks:
• One notebook (hash map) tracks what word each letter gets—like "a: dog."
• Another tracks what letter each word gets—like "dog: a."
• Step 4: Pair Them Up:
• Go through the pattern and words together (like "a" with "dog," "b" with "cat"):
• Check the letter’s notebook: If "a" already has "dog," cool. If it has "fish" instead, mismatch—stop.
• Check the word’s notebook: If "dog" already has "a," cool. If it has "b," mismatch—stop.
• If both are new, write them in: "a → dog" and "dog → a."
• Step 5: Why It Works:
• Two maps ensure each letter sticks to one word and each word sticks to one letter—like a two-way promise.
• If anything breaks the pattern (like "a" mapping to two words), we catch it right away.

It’s like making sure every friend has a unique nickname, and every nickname has one friend!

Step-by-Step Example

Example: pattern = "abba", s = "dog cat cat dog"

• Split: Words = ["dog", "cat", "cat", "dog"].
• Length Check: Pattern = 4, words = 4—good!
• Pairing:
• "a" and "dog": Letter map = {"a": "dog"}, Word map = {"dog": "a"}.
• "b" and "cat": Letter map = {"a": "dog", "b": "cat"}, Word map = {"dog": "a", "cat": "b"}.
• "b" and "cat": Letter map has "b" → "cat," Word map has "cat" → "b"—matches, keep going.
• "a" and "dog": Letter map has "a" → "dog," Word map has "dog" → "a"—matches.
• Result: All pairs match → True.

Example: pattern = "abba", s = "dog cat cat fish"

• Pairing:
• "a" → "dog": {"a": "dog"}, {"dog": "a"}.
• "b" → "cat": {"a": "dog", "b": "cat"}, {"dog": "a", "cat": "b"}.
• "b" → "cat": Matches.
• "a" → "fish": "a" already maps to "dog," not "fish"—mismatch → False.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # Step 1: Split the string into words
        words = s.split()  # Turns "dog cat" into ["dog", "cat"]

        # Step 2: Check if lengths match
        if len(pattern) != len(words):
            return False  # Different sizes? No match!

        # Step 3: Make two notebooks (hash maps)
        letter_to_word = {}  # Like "a" → "dog"
        word_to_letter = {}  # Like "dog" → "a"

        # Step 4: Check each pair
        for p, w in zip(pattern, words):  # Pair "a" with "dog", etc.
            # If letter has a word, it must match this word
            if p in letter_to_word:
                if letter_to_word[p] != w:
                    return False  # "a" can’t be "dog" and "fish"
            # If word has a letter, it must match this letter
            elif w in word_to_letter:
                if word_to_letter[w] != p:
                    return False  # "dog" can’t be "a" and "b"
            # New pair, add to both notebooks
            else:
                letter_to_word[p] = w
                word_to_letter[w] = p

        # Step 5: All pairs matched!
        return True

• Line 4: Split s into a list of words—like turning a sentence into a list.
• Line 7-8: If pattern and word list lengths don’t match, it’s over—return False.
• Line 10-11: Set up two empty hash maps—one for each direction.
• Line 14-23: Loop through pattern and words together:
• If the letter’s already mapped, check it matches this word.
• If the word’s already mapped, check it matches this letter.
• If neither’s mapped, add the pair to both maps.
• Line 25: If we get here, everything matched—return True!

• Time Complexity: O(n)—one pass through the pattern and words.
• Space Complexity: O(n)—two hash maps store the mappings.

This is like a perfect buddy system—everyone’s paired up right!

Alternative Solution: Single Hash with List Tracking

Why an Alternative Approach?

The single hash with list tracking uses one hash map and compares word positions—still O(n) time and O(n) space—but it’s a bit simpler to set up. It maps letters to words and checks if the word list matches the pattern’s order. It’s like keeping a single notebook and double-checking the lineup.

How It Works

Let’s picture this as a lineup check:

• Step 1: Split s into words.
• Step 2: Check lengths match.
• Step 3: Map letters to words in a hash map.
• Step 4: Build a list of mapped words from the pattern and compare it to the original word list.

It’s like making a checklist and seeing if it lines up!

Step-by-Step Example

Example: pattern = "abba", s = "dog cat cat dog"

• Words: ["dog", "cat", "cat", "dog"].
• Length: 4 = 4—good.
• Map: "a" → "dog," "b" → "cat."
• Build: "abba" → ["dog", "cat", "cat", "dog"]—matches words → True.

Example: pattern = "abba", s = "dog dog dog dog"

• Map: "a" → "dog," "b" → "dog"—mismatch, "b" should be different → False.

Code for Single Hash with List Tracking

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

        mapping = {}
        for p, w in zip(pattern, words):
            if p not in mapping:
                # If word’s already used for another letter, fail
                if w in mapping.values():
                    return False
                mapping[p] = w
            elif mapping[p] != w:
                return False

        return True

• Time Complexity: O(n)—one pass, but checking values is O(n) in worst case.
• Space Complexity: O(n)—one hash map.

It’s a simpler check but less explicit about two-way mapping.

Comparing the Two Solutions

• Two-Way Hash (Best):
• Pros: O(n) time, O(n) space, clear two-way check.
• Cons: Two maps to manage.
• Single Hash (Alternative):
• Pros: O(n) time, O(n) space, one map.
• Cons: Less direct, value check can slow it.

Two-way wins for clarity and speed.

Additional Examples and Edge Cases

• "a", "dog": True.
• "ab", "dog": False (length mismatch).
• "abc", "dog dog dog": False.

Both handle these well.

Complexity Breakdown

• Two-Way: Time O(n), Space O(n).
• Single Hash: Time O(n), Space O(n).

Two-way is the champ.

Key Takeaways

• Two-Way: Double-check mappings—perfect!
• Single Hash: One map, still works—simple!
• Patterns: Matching is fun.
• Python Tip: Dictionaries rock—see [Python Basics](/python/basics).

Final Thoughts: Match That Pattern

LeetCode 290: Word Pattern in Python is a delightful matching game. The two-way hash solution nails it with precision, while the single hash offers an easy start. Want more? Try LeetCode 205: Isomorphic Strings or LeetCode 49: Group Anagrams. Ready to pair up? Head to Solve LeetCode 290 on LeetCode and match those patterns today!