NUHMAN.com

Introduction

LeetCode 291: Word Pattern II is an extension of LeetCode 290: Word Pattern, where we are asked to match a given pattern to a string s in a more complex way. In this problem, the pattern consists of lowercase English letters, and we need to check if there is a bijective mapping (one-to-one and onto mapping) between the characters in the pattern and substrings of the string s.

The main challenge here is that, unlike LeetCode 290, where the mapping is simple, this problem requires us to assign distinct substrings to the characters in the pattern using backtracking. Each character in the pattern must be mapped to a unique substring of s.

Problem Statement

Given a string pattern and a string s, return true if there is a bijective mapping from the characters in the pattern to substrings of s. A bijection means:

• Each character in pattern maps to a unique substring of s.
• No two characters map to the same substring.

You need to check if it's possible to partition s into substrings that match the pattern.

Example

python

Input:
pattern = "abab"
s = "redblueredblue"

Output:
true

Explanation:
The pattern "abab" can match the string "redblueredblue" as follows:
'a' -> "red"
'b' -> "blue"
'a' -> "red"
'b' -> "blue"
python

Input:
pattern = "aaaa"
s = "asdasd"

Output:
false

Explanation:
The pattern "aaaa" cannot match the string "asdasd" because there is no way to partition "asdasd" into 4 substrings that all match "a".

✅ Step-by-Step Solution

🧠 Intuition

The main difference between LeetCode 290 and LeetCode 291 is that here we need to find substrings, and the solution involves backtracking. We must try every possible substring mapping for each character in the pattern and check if the resulting assignments are consistent.

Key steps:

1. Backtracking: We try every possible substring of s for each character in the pattern and check if the remaining string and remaining pattern characters can still be matched.
2. Tracking the Mapping: We keep track of which characters have already been assigned to which substrings and vice versa to ensure the mapping is bijective.
3. Return True/False: We return true if we successfully match the entire string s to the entire pattern, and false otherwise.

✅ Approach

1. Backtracking:

• For each character in the pattern, try to map it to all possible substrings of s that haven't been used yet.
• If a substring is successfully mapped, proceed recursively to the next character.
• If at any point the mapping becomes inconsistent, backtrack and try a different mapping.

1. Recursive Function:

• The base case is when we have successfully matched all characters in the pattern and exhausted the string s.
• If we reach the end of the pattern or string and haven't successfully matched, return false.

1. Mapping Validation:

• Ensure that no two characters in the pattern map to the same substring.
• Ensure that no character is mapped to multiple substrings.

✅ Python Code

python

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        # Helper function to perform backtracking
        def backtrack(i, j, pattern_to_word, word_to_pattern):
            # If both the pattern and the string are exhausted, return True
            if i == len(pattern) and j == len(s):
                return True
            # If one is exhausted but not the other, return False
            if i == len(pattern) or j == len(s):
                return False

            char = pattern[i]
            # Try all possible substrings of s starting at position j
            for k in range(j + 1, len(s) + 1):
                word = s[j:k]
                # Check if the current pattern character is already mapped
                if char in pattern_to_word:
                    # If it's mapped to a different word, skip
                    if pattern_to_word[char] != word:
                        continue
                # Check if the current word is already mapped to a different pattern character
                elif word in word_to_pattern:
                    # If it's mapped to a different character, skip
                    if word_to_pattern[word] != char:
                        continue
                else:
                    # Create a new mapping
                    pattern_to_word[char] = word
                    word_to_pattern[word] = char
                    # Recursively check the next pattern character and the next part of the string
                    if backtrack(i + 1, k, pattern_to_word, word_to_pattern):
                        return True
                    # Backtrack by removing the mapping
                    del pattern_to_word[char]
                    del word_to_pattern[word]

            return False

        return backtrack(0, 0, {}, {})

🧪 How It Works

1. Backtracking Function:

• We define a helper function backtrack(i, j, pattern_to_word, word_to_pattern) where i is the current index in the pattern and j is the current index in the string s.
• We attempt to match each pattern character to all possible substrings starting from index j.

1. Mapping Validation:

• For each substring, we check if the pattern character is already mapped to a word, and if so, whether it matches the current word. Similarly, we check the reverse mapping from word to pattern character.

1. Base and Recursive Cases:

• Base Case: If both the pattern and the string are fully traversed, return true. If either is exhausted while the other still has characters left, return false.
• Recursive Case: For each possible substring, check if it fits the current pattern character and proceed recursively. If at any point a conflict arises, backtrack and try another substring.

1. Backtracking:

• After trying a substring, we backtrack by removing the current mappings and trying the next possible substring.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(2^(n + m)), where n is the length of the pattern and m is the length of the string s. The complexity arises from the need to try different substrings for each character, leading to exponential growth in the number of possibilities to explore.Space ComplexityO(n + m), where n is the length of the pattern and m is the length of the string. The space complexity comes from storing the mappings (pattern-to-word and word-to-pattern) in the dictionaries.

• The time complexity is exponential due to the nature of backtracking, where we try every possible substring for each pattern character.
• The space complexity is O(n + m) for storing the mappings.

🔍 Edge Cases

1. Empty String and Pattern: If both the string and the pattern are empty, the function should return true, as they trivially match.
2. Different Lengths: If the length of the pattern does not match the length of the string s, return false.
3. Unmatched Pattern: If it is impossible to create a valid mapping (for example, if the pattern has more characters than available unique substrings in s), return false.
4. Partial Matching: If the pattern can be partially matched but not completely, return false.

✅ Conclusion

LeetCode 291: Word Pattern II is a challenging problem that requires backtracking to find if there is a valid mapping between the characters of a pattern and substrings of a string. By exploring all possible substring mappings for each character and validating the mappings, we can determine if the pattern matches the string.

This problem is a great exercise in recursion, backtracking, and managing bijective relationships between characters and substrings.