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

What Is LeetCode 291: Word Pattern II?

In LeetCode 291: Word Pattern II, you’re given a string pattern (like "abab") and a string str (like "redbluebluered"), and your task is to check if str can be split into substrings that match pattern. Each letter in the pattern maps to a unique substring, and each substring maps back to a unique letter—like a two-way deal. Unlike LeetCode 290, where words are pre-split, here you decide how to cut str. For example, "abab" matches "redbluebluered" if 'a' → "red" and 'b' → "blue." This problem tests your ability to explore possibilities, feeling a bit like LeetCode 290: Word Pattern but with more freedom and complexity.

Problem Statement

• Input: A string pattern and a string str.
• Output: True if str can be segmented to match pattern, False otherwise.
• Rules: Each pattern letter maps to one substring; each substring maps to one letter; mappings must be consistent.

Constraints

• pattern length: 1 to 20.
• str length: 1 to 20.
• Both contain only lowercase English letters.

Examples

• Input: pattern = "abab", str = "redbluebluered"
• Output: True ('a' → "red", 'b' → "blue")
• Input: pattern = "aaaa", str = "asdasdasdasd"
• Output: True ('a' → "asd")
• Input: pattern = "abab", str = "redblueredblue"
• Output: False (no consistent mapping)
• Input: pattern = "a", str = "cat"
• Output: True ('a' → "cat")

Understanding the Problem: Slicing to Match

To solve LeetCode 291: Word Pattern II in Python, we need to see if str can be chopped into pieces that match pattern, where each letter gets its own substring, and no two letters share the same one. For "abab" and "redbluebluered," we try 'a' as "red" and 'b' as "blue," checking if it fits: "red" + "blue" + "blue" + "red." The string’s length and pattern must align, but we get to pick the cuts. A slow way would be to try every possible split, but we’ll use smarter ideas:

• Best Solution (Backtracking with Hash Mapping): O(n * 2^n) time, O(n) space—fast and flexible.
• Alternative Solution (Brute-Force Substrings): O(2^n * n) time—simpler but super slow.

Let’s jump into the backtracking solution with a friendly breakdown that’s easy to follow.

Best Solution: Backtracking with Hash Mapping

Why This Is the Best Solution

The backtracking with hash mapping approach is the best for LeetCode 291 because it’s efficient for this problem’s size—O(n * 2^n) time, where n is the string length—and uses O(n) space with two hash maps. It tries possible substring mappings step-by-step, backing off when they don’t work, and checks both ways (letter-to-string and string-to-letter) to ensure a perfect fit. It’s like exploring a maze with a map, turning back if you hit a dead end—smart and manageable!

How It Works

Let’s imagine this like a puzzle where we’re fitting pieces:

• Step 1: Set Up Tools:
• Use two notebooks (hash maps): one for pattern letters to substrings (like "a → red"), one for substrings to letters (like "red → a").
• Step 2: Explore with a Helper:
• Start at the beginning of the pattern and string (position 0 for both).
• For each pattern letter, try different substring lengths from the current string position.
• Step 3: Try and Backtrack:
• Pick a substring for the current letter (e.g., "red" for 'a').
• Check the notebooks:
• If 'a' already maps to "red" and "red" maps to 'a,' move on.
• If 'a' maps to something else or "red" maps to another letter, skip this try.
• If new, add to both notebooks and try the next letter.
• If it doesn’t work (string runs out or mappings clash), undo and try a longer substring.
• Step 4: Finish or Fail:
• If you match the whole pattern and use all the string, it’s True.
• If no combination works, it’s False.
• Step 5: Why It Works:
• Backtracking tries all valid possibilities without wasting time.
• Two-way mapping ensures each letter and substring pair up uniquely.

It’s like trying puzzle pieces, keeping what fits and swapping when it doesn’t!

Step-by-Step Example

Example: pattern = "abab", str = "redbluebluered"

• Start: p_idx=0, s_idx=0, maps empty.
• p_idx=0, 'a':
• Try "r": Too short, skip.
• Try "red": Add "a → red," "red → a," next p_idx=1, s_idx=3.
• p_idx=1, 'b':
• Try "b": Skip.
• Try "blue": Add "b → blue," "blue → b," p_idx=2, s_idx=7.
• p_idx=2, 'a':
• Try "blue": "a" already "red," mismatch, skip.
• Backtrack to 'b', try "blu": "b → blu," "blu → b," p_idx=2, s_idx=6.
• p_idx=2, 'a':
• Try "e": Skip.
• Backtrack, adjust earlier cuts—retry "b" as "blue," then "a" as "bluered" fails length.
• Correct path: "a → red," "b → blue," check "blue" (matches 'b'), "red" (matches 'a').
• Finish: p_idx=4, s_idx=14—matches → True.

Code with Detailed Line-by-Line Explanation

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

class Solution:
    def wordPatternMatch(self, pattern: str, str: str) -> bool:
        # Step 1: Set up two notebooks
        p_to_s = {}  # Pattern letter to substring
        s_to_p = {}  # Substring to pattern letter

        # Step 2: Helper to try mappings
        def backtrack(p_idx, s_idx):
            # If we’ve used all pattern and string, success!
            if p_idx == len(pattern) and s_idx == len(str):
                return True
            # If one runs out before the other, fail
            if p_idx >= len(pattern) or s_idx >= len(str):
                return False

            curr_p = pattern[p_idx]  # Current pattern letter
            # Try all possible substrings from s_idx
            for i in range(s_idx, len(str)):
                sub = str[s_idx:i + 1]  # Substring to try
                # If letter’s mapped
                if curr_p in p_to_s:
                    if p_to_s[curr_p] == sub:  # Matches, try next
                        if backtrack(p_idx + 1, i + 1):
                            return True
                # If new mapping
                else:
                    if sub not in s_to_p:  # Substring unused
                        p_to_s[curr_p] = sub
                        s_to_p[sub] = curr_p
                        if backtrack(p_idx + 1, i + 1):
                            return True
                        # Undo if it fails
                        del p_to_s[curr_p]
                        del s_to_p[sub]
            return False

        # Step 3: Start the search
        return backtrack(0, 0)

• Line 4-5: Two empty hash maps for two-way mapping.
• Line 8-30: Helper backtrack:
• Line 10-13: Success if both are fully used; fail if one runs out early.
• Line 15: Get the current pattern letter.
• Line 17-28: Try substrings:
• Take a slice from s_idx to i.
• If letter’s mapped, check it fits; if yes, try next letter.
• If new, check substring’s free, add to maps, try next, undo if it fails.
• Line 32: Kick off from start.

• Time Complexity: O(n * 2^n)—exponential due to substring tries.
• Space Complexity: O(n)—maps and recursion stack.

This is like a puzzle-solving adventure—try, adjust, win!

Alternative Solution: Brute-Force Substring Generation

Why an Alternative Approach?

The brute-force method generates all possible ways to split str and checks each against pattern—O(2^n * n) time, O(n) space. It’s slow and impractical for big inputs but shows the raw idea, like trying every way to cut a cake until one fits.

How It Works

Imagine slicing the string every way possible:

• Step 1: Generate all splits of str (e.g., "redblue" → [["r", "e", "d", "b", "l", "u", "e"], ["re", "db", "lue"], ...]).
• Step 2: For each split with the right number of parts:
• Map pattern letters to substrings.
• Check if it matches both ways.
• Step 3: Return True if any split works.

It’s like brute-forcing a lock—try everything!

Step-by-Step Example

Example: pattern = "ab", str = "redblue"

• Splits: ["r", "edblue"], ["re", "dblue"], ["red", "blue"], etc.
• Check "red", "blue": "a → red," "b → blue"—works, rebuilds "redblue" → True.

Code for Brute-Force Approach

class Solution:
    def wordPatternMatch(self, pattern: str, str: str) -> bool:
        def generate_splits(s, parts):
            if parts == 1:
                return [[s]]
            result = []
            for i in range(1, len(s) - parts + 2):
                prefix = s[:i]
                for rest in generate_splits(s[i:], parts - 1):
                    result.append([prefix] + rest)
            return result

        splits = generate_splits(str, len(pattern))
        for split in splits:
            p_to_s, s_to_p = {}, {}
            match = True
            for p, s in zip(pattern, split):
                if p in p_to_s:
                    if p_to_s[p] != s:
                        match = False
                        break
                elif s in s_to_p:
                    match = False
                    break
                p_to_s[p] = s
                s_to_p[s] = p
            if match:
                return True
        return False

• Time Complexity: O(2^n * n)—exponential splits and checks.
• Space Complexity: O(n)—maps and recursion.

It’s a slow slog but gets there.

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(n * 2^n) time, O(n) space, prunes bad paths.
• Cons: Recursive complexity.
• Brute-Force (Alternative):
• Pros: O(2^n * n) time, straightforward.
• Cons: Super slow, impractical.

Backtracking wins big.

Additional Examples and Edge Cases

• "a", "x": True.
• "ab", "xy": True.
• "ab", "xx": False.

Both handle these, but backtracking’s faster.

Complexity Breakdown

• Backtracking: Time O(n * 2^n), Space O(n).
• Brute-Force: Time O(2^n * n), Space O(n).

Backtracking rules.

Key Takeaways

• Backtracking: Try and adjust—smart!
• Brute-Force: Try everything—slow!
• Patterns: Flexible matching is cool.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Slice That Pattern

LeetCode 291: Word Pattern II in Python is a brain-teasing word puzzle. Backtracking cuts through efficiently, while brute-force shows the raw idea. Want more? Try LeetCode 290: Word Pattern or LeetCode 139: Word Break. Ready to match? Head to Solve LeetCode 291 on LeetCode and slice that string today!