Solution Explanation for Word Pattern II

This problem asks whether a given string s matches a given pattern. Matching means there's a one-to-one mapping between characters in the pattern and non-empty substrings in the string. This requires a backtracking approach because we need to explore all possible mappings.

Approach

The solution uses a depth-first search (DFS) or backtracking algorithm to explore all possible mappings between pattern characters and substrings of the input string.

1. Base Cases:

   • If we've reached the end of both the pattern and the string, it's a match (return true).
   • If we've reached the end of the pattern but not the string, or if there aren't enough characters remaining in the string to match the rest of the pattern, it's not a match (return false).

2. Recursive Step:

   • For each character in the pattern, we iterate through possible substrings in the input string starting from the current position.
   • Check Existing Mapping: If the character in the pattern already has a mapping in our d dictionary, we check if the current substring matches that mapping. If it does, we recursively call dfs to continue checking the rest of the pattern and string.
   • Try New Mapping: If the character doesn't have a mapping or the substring doesn't match an existing mapping, and the substring is not already used in the vis set (to ensure bijective mapping), we create a new mapping, add the substring to vis, recursively call dfs, and then backtrack by removing the mapping and substring to explore other possibilities.

3. Backtracking: The crucial part of this approach is backtracking. After trying a mapping and the recursive call returns false, we need to undo that mapping to try other possibilities. This is done by removing the mapping from d and the substring from vis.

Time and Space Complexity Analysis

Time Complexity: O(N * M * 2M), where N is the length of the string s and M is the length of the pattern p. The exponential part comes from exploring different mappings for each character in the pattern, in the worst case.

Space Complexity: O(M) The space is dominated by the d dictionary (mapping pattern characters to substrings) and the vis set (to track used substrings), both of which have sizes at most proportional to the length of the pattern. The recursion depth is also at most proportional to M.

Code Explanation (Python)

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def dfs(i, j):
            if i == m and j == n:
                return True
            if i == m or j == n or n - j < m - i: # optimization: if remaining string length is less than remaining pattern length
                return False
            for k in range(j, n):
                t = s[j : k + 1]
                if d.get(pattern[i]) == t:
                    if dfs(i + 1, k + 1):
                        return True
                if pattern[i] not in d and t not in vis:
                    d[pattern[i]] = t
                    vis.add(t)
                    if dfs(i + 1, k + 1):
                        return True
                    d.pop(pattern[i])
                    vis.remove(t)
            return False
 
        m, n = len(pattern), len(s)
        d = {}  # Mapping from pattern characters to substrings
        vis = set() # Set of used substrings
        return dfs(0, 0)

The other languages (Java, C++, Go) follow a similar structure, using their respective data structures for dictionaries and sets. The core logic of the backtracking DFS remains the same.