LeetCode 291 - Word Pattern II

The problem asks us to determine whether a given string s can be formed by substituting each character in a pattern with a non-empty string, under a bijective mapping.

leetcodemediumhash-tablestringbacktracking

LeetCode Problem 291

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking

Solution

Problem Understanding

The problem asks us to determine whether a given string s can be formed by substituting each character in a pattern with a non-empty string, under a bijective mapping. Bijective means that every character maps to exactly one unique substring and no two characters map to the same substring. Essentially, each character in the pattern is a placeholder for a distinct string in s.

The inputs are straightforward: pattern is a short string of lowercase letters representing the mapping keys, and s is a target string that may be reconstructed using this mapping. The output is a boolean, true if such a mapping exists, or false if it does not.

The constraints are small (1 <= pattern.length, s.length <= 20), which implies that solutions using backtracking or recursion are feasible despite potentially high time complexity. Important edge cases include patterns where all characters are the same, patterns longer than the string, or strings that cannot be split to satisfy the mapping. The problem guarantees non-empty strings and lowercase letters only, so we do not need to handle empty inputs or invalid characters.

Approaches

The brute-force approach would try every possible split of s for each character in pattern. For each character, we attempt all substrings of s and recursively check if the remaining substring matches the remaining pattern, keeping track of used mappings. While this guarantees a correct answer, the number of combinations grows exponentially with the length of the string and pattern. For example, if the pattern is length n and string is length m, there could be up to $O(m^n)$ combinations.

The key insight for an optimal solution is to use backtracking with a hash map to enforce the bijective mapping. We maintain two mappings: one from pattern characters to substrings and another from substrings to pattern characters. When a mapping is already assigned, we check consistency. If not, we try all possible substring assignments for the current character and recurse. Backtracking ensures that all potential mappings are explored but invalid paths are pruned early when inconsistencies are detected.

Approach Time Complexity Space Complexity Notes
Brute Force O(m^n) O(n) Tries all possible substring splits for each character in pattern
Backtracking with Hash Map O(n * 2^m) O(n + m) Recursively assigns substrings with early pruning and maintains bijective mapping

Algorithm Walkthrough

  1. Initialize two hash maps: one for mapping pattern characters to substrings (char_to_word) and another for substrings to characters (word_to_char). This ensures the bijective property.
  2. Define a recursive function dfs(i, j) where i is the current index in the pattern and j is the current index in the string s.
  3. If i equals the length of the pattern and j equals the length of s, return true because a complete mapping was successfully found.
  4. If i equals the length of the pattern but j does not, or vice versa, return false because the pattern and string lengths are inconsistent with any mapping.
  5. Check if the current pattern character already has a mapping:
  • If yes, retrieve the mapped substring and check if the corresponding part of s matches it. If it does, recursively call dfs for the next indices. If not, return false.
  1. If the current character does not have a mapping, try assigning every possible substring starting from index j to the current pattern character:
  • Skip substrings already mapped to another pattern character.
  • Assign the substring and recursively call dfs for the next indices.
  • If the recursion returns true, propagate it. Otherwise, backtrack by removing the assignment.
  1. If all substring options are exhausted without a valid mapping, return false.

Why it works: This algorithm systematically explores all valid mappings while ensuring bijectivity. Backtracking ensures that invalid paths are abandoned early, which prevents unnecessary computation and guarantees correctness.

Python Solution

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def dfs(i: int, j: int, char_to_word: dict, word_to_char: dict) -> bool:
            if i == len(pattern) and j == len(s):
                return True
            if i == len(pattern) or j == len(s):
                return False
            
            char = pattern[i]
            
            if char in char_to_word:
                word = char_to_word[char]
                if not s.startswith(word, j):
                    return False
                return dfs(i + 1, j + len(word), char_to_word, word_to_char)
            
            for end in range(j + 1, len(s) + 1):
                word = s[j:end]
                if word in word_to_char:
                    continue
                char_to_word[char] = word
                word_to_char[word] = char
                if dfs(i + 1, end, char_to_word, word_to_char):
                    return True
                del char_to_word[char]
                del word_to_char[word]
            
            return False
        
        return dfs(0, 0, {}, {})

The Python implementation uses a recursive helper function dfs that explores all possible mappings. The two hash maps char_to_word and word_to_char enforce the bijective mapping. Substrings already assigned are skipped to avoid conflicts, and backtracking ensures incorrect assignments are removed.

Go Solution

func wordPatternMatch(pattern string, s string) bool {
    charToWord := make(map[byte]string)
    wordToChar := make(map[string]byte)
    
    var dfs func(int, int) bool
    dfs = func(i int, j int) bool {
        if i == len(pattern) && j == len(s) {
            return true
        }
        if i == len(pattern) || j == len(s) {
            return false
        }
        
        char := pattern[i]
        if word, ok := charToWord[char]; ok {
            if j+len(word) > len(s) || s[j:j+len(word)] != word {
                return false
            }
            return dfs(i+1, j+len(word))
        }
        
        for end := j + 1; end <= len(s); end++ {
            word := s[j:end]
            if _, exists := wordToChar[word]; exists {
                continue
            }
            charToWord[char] = word
            wordToChar[word] = char
            if dfs(i+1, end) {
                return true
            }
            delete(charToWord, char)
            delete(wordToChar, word)
        }
        
        return false
    }
    
    return dfs(0, 0)
}

The Go solution mirrors the Python approach, using map[byte]string for charToWord and map[string]byte for wordToChar. Go requires careful handling of slice indices when checking substring matches.

Worked Examples

Example 1: pattern = "abab", s = "redblueredblue"

Step i j char_to_word word_to_char Action
1 0 0 {} {} Assign 'a' -> "red"
2 1 3 {'a':'red'} {'red':'a'} Assign 'b' -> "blue"
3 2 7 {'a':'red', 'b':'blue'} {'red':'a','blue':'b'} Check 'a' maps to "red" at index 7
4 3 10 {'a':'red','b':'blue'} {'red':'a','blue':'b'} Check 'b' maps to "blue" at index 10
5 4 14 success Entire pattern matched

Example 2: pattern = "aaaa", s = "asdasdasdasd"

Step i j char_to_word word_to_char Action
1 0 0 {} {} Assign 'a' -> "asd"
2 1 3 {'a':'asd'} {'asd':'a'} Check 'a' maps to "asd" at indices 3,6,9
3 4 12 success Entire pattern matched

Example 3: pattern = "aabb", s = "xyzabcxzyabc"

Step i j char_to_word word_to_char Action
1 0 0 {} {} Try all possible splits
2 ... ... ... ... No combination satisfies bijection
3 end end Return false

Complexity Analysis

Measure Complexity Explanation
Time O(n * 2^m) For each character, we may try all substrings, pruning invalid paths early
Space O(n + m) Hash maps store mappings, recursion stack can go as deep as pattern length

The time complexity is exponential in the length of s due to substring splitting, but the constraints (≤ 20)