291. Word Pattern II

MediumHash TableStringBacktracking
Leetcode Link

Problem Description

In this problem, we're given a pattern, which is a string consisting of characters, and a string s. Our goal is to determine if the string s matches the given pattern.

A string s is considered to match a pattern if we can associate each character in pattern with a non-empty string in s such that the concatenation of the strings, in the order they appear in pattern, exactly makes up s. The mapping must be bijective, which means two conditions must be met: first, no two different characters in pattern can map to the same substring in s, and second, each character must map to exactly one substring (and not multiple different substrings at different instances).

For example, if pattern is "abab" and s is "redblueredblue" then we could map 'a' to "red" and 'b' to "blue", which matches the pattern.

Intuition

Approaching the solution requires a way to test different mappings from pattern characters to substrings of s. Since the problem's constraints don't offer an obvious pattern or formula, we opt for a strategy that tries out different possibilities—this is a typical case for using a backtracking algorithm.

The intuition behind the solution is to recursively attempt to build a mapping between each character in pattern and the substrings of s. We start by considering the first character in the pattern and try to map it to all possible prefixes of the string s. For each mapping we consider, we recursively attempt to extend the mapping to the rest of the characters in the pattern. If at any point, we find a complete and valid mapping, we return true.

If we ever reach a situation where a character is already mapped to a different string, or if we try to associate a substring with a pattern character that is already taken by another substring, we backtrack. We also stop exploring the current recursive branch if we exhaust the characters in pattern or s, or if the remaining length of s is too short to cover the remaining characters in pattern. This process continues until either a full mapping is found or all possibilities have been exhausted, which would lead us to conclude that no valid mapping exists.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the maximum element can be found in:

Solution Approach

The provided solution uses a recursive backtracking approach to implement the logic described in the intuition section. Let's examine the implementation in detail:

  1. Depth-First Search (DFS) with Backtracking:

    • The dfs function is a recursive function that keeps track of the current position i in the pattern and the current position j in the string s.
    • If i equals the length of pattern (m) and j equals the length of s (n), it means we have successfully mapped the entire pattern to the string s, and we return True.
    • If either i equals m or j equals n before the other, or if there aren't enough characters left in s to match the remaining pattern (n - j < m - i), we return False as it signifies that the current mapping does not cover s or pattern correctly.

  2. Attempt to Match Substrings:

    • The dfs function iterates over the substring of s starting from index j and ending at various points k within the string. This loop essentially tries to map the current pattern character to various lengths of substrings in s.
    • We extract the current substring of s from index j to k and store it in a variable t.
    • If the current pattern character at index i already has a mapping in the dictionary d and it is equal to t, we recursively call dfs for the next character in the pattern and the next part of the string. If this returns True, then the current mapping is part of a solution, and we propagate this success back up the recursion chain.

  3. Adding New Mappings:

    • If the current pattern character at index i is not yet mapped in the dictionary d and the substring t is not already used (checked using set vis), we add the mapping pattern[i] -> t to d and add t to vis.
    • We then recurse to see if this new mapping could lead to a solution.
    • Whether the recursive call returns True or False, we then backtrack by removing the current mapping from d and t from vis, allowing the next iteration to try a different mapping for the same pattern character.

  4. Data Structures:

    • A dictionary d is used to keep track of the current mapping from pattern characters to substrings in s.
    • A set vis is used to keep track of the substrings of s that have already been mapped to some pattern characters. This helps ensure the bijective nature of the mapping.

  5. Initiating the Recursive Search:

    • Before starting the backtracking process, we initialize the variables m and n to hold the lengths of pattern and s, respectively. The dictionary d and the set vis are initialized to be empty.
    • The dfs function is then initiated with i and j both set to 0, which signifies the start of pattern and s.

In conclusion, the recursive backtracking approach is quite fitting for this problem, as it allows the solution to explore all possible mappings and backtrack as soon as it detects a mapping scenario that cannot lead to a successful pattern match. This approach is particularly powerful for problems related to pattern matching, permutations, and combinations where all potential scenarios need to be considered.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the pattern "aba" and the string s "catdogcat".

  1. Start with the First Character in Pattern:

    • We examine the first character in the pattern, which is 'a'.
    • We try to map 'a' to each possible prefix of the string s. This means we initially consider 'c', 'ca', 'cat', 'catd', 'catdo', 'catdog', 'catdogc', 'catdogca', and 'catdogcat'.

  2. First Recursive Branch - 'a' Mapped to 'c':

    • On the first attempt, we associate 'a' with 'c' and then recurse to the next character in the pattern.
    • Now, our pattern looks like "c_b_c" with 'b' unassigned, and the remaining part of the string is "atdogcat".
    • Next, we attempt to map 'b' to 'a', but this leaves us with "c_ac_c", and the remaining string is "tdogcat", which no longer has a viable place to map the next 'a', as the next 'a' in the pattern would be mapped to 't'. Since 't' is not equal to our existing mapping of 'a', we must backtrack.

  3. Second Recursive Branch - 'a' Mapped to 'ca':

    • Backtracking from the previous step, we now try to map 'a' to 'ca'.
    • Following a similar pattern to the step above, we look at the next character 'b' and attempt to map it to 't', and then 'd', and then 'do', and so on until 'tdog'.
    • Every time, we check if the subsequent character in the pattern ('a') can continue with the already established mapping ('ca'). If not, we continue.

  4. Successful Recursive Branch - 'a' Mapped to 'cat':

    • Continuing to explore, we finally map 'a' to 'cat'.
    • Our pattern now looks like "cat_b_cat", and the remaining string is "dog".
    • We map 'b' to 'dog', as it's the only substring left that fits.
    • The full string according to our pattern and mapping is "catdogcat", which matches s.
    • Since we've successfully mapped the entire pattern to the string s without any conflicting mappings, the algorithm would return True.

Throughout the process, the algorithm uses a dictionary to maintain the mapping of pattern characters to substrings in s and a set to ensure that no two characters in the pattern map to the same substring. If at any point the mapping is not consistent or a character cannot be mapped to a remaining substring without conflict, the algorithm backtracks and tries a different mapping. In this example, we eventually found a successful mapping that satisfies the requirement of the problem.

Solution Implementation

1class Solution:
2    def wordPatternMatch(self, pattern: str, string: str) -> bool:
3        # Recursive function to check pattern match
4        def backtrack(pattern_index, string_index):
5            # Base case: when both pattern and string are completely matched
6            if pattern_index == pattern_length and string_index == string_length:
7                return True
8            # If one is finished before the other, or if the remaining string is 
9            # shorter than the remaining pattern, it's not a match
10            if pattern_index == pattern_length or string_index == string_length or \
11               string_length - string_index < pattern_length - pattern_index:
12                return False
13          
14            for end_index in range(string_index, string_length):
15                # Get the current substring
16                current_substring = string[string_index : end_index + 1]
17                # Check if it matches the pattern's current token
18                if pattern_to_string.get(pattern[pattern_index]) == current_substring:
19                    # Continue to the next token
20                    if backtrack(pattern_index + 1, end_index + 1):
21                        return True
22                # If it's a new pattern token and substring, try to map them
23                if pattern[pattern_index] not in pattern_to_string and \
24                   current_substring not in used_substrings:
25                    # Add the new mapping
26                    pattern_to_string[pattern[pattern_index]] = current_substring
27                    used_substrings.add(current_substring)
28                    # Continue to the next token
29                    if backtrack(pattern_index + 1, end_index + 1):
30                        return True
31                    # Backtrack: remove the added mapping if it didn't lead to a solution
32                    pattern_to_string.pop(pattern[pattern_index])
33                    used_substrings.remove(current_substring)
34            # If no solution was found after trying all options
35            return False
36
37        # Lengths of the input pattern and string
38        pattern_length, string_length = len(pattern), len(string)
39        # Dictionary to keep track of the mapping from pattern to string
40        pattern_to_string = {}
41        # Set to keep track of already used substrings
42        used_substrings = set()
43        # Start the recursion
44        return backtrack(0, 0)
45
1class Solution {
2    // A set to maintain the unique substrings that are already mapped.
3    private Set<String> visited;
4  
5    // A map to maintain the mapping from a pattern character to its corresponding substring.
6    private Map<Character, String> patternMapping;
7  
8    // The pattern string that needs to be matched.
9    private String pattern;
10  
11    // The string that we are trying to match against the pattern.
12    private String str;
13  
14    // The length of the pattern string.
15    private int patternLength;
16  
17    // The length of the string str.
18    private int stringLength;
19
20    public boolean wordPatternMatch(String pattern, String str) {
21        visited = new HashSet<>();
22        patternMapping = new HashMap<>();
23        this.pattern = pattern;
24        this.str = str;
25        patternLength = pattern.length();
26        stringLength = str.length();
27        // Initiate the depth-first search from the beginning of both the pattern and the str.
28        return depthFirstSearch(0, 0);
29    }
30
31    // A helper function to perform the depth-first search.
32    private boolean depthFirstSearch(int patternIndex, int strIndex) {
33        // If we reach the end of both the pattern and the str, we have found a match.
34        if (patternIndex == patternLength && strIndex == stringLength) {
35            return true;
36        }
37        // If we reach the end of one without the other, or there are more characters to match in the pattern than the remaining length of str, we cannot have a match.
38        if (patternIndex == patternLength || strIndex == stringLength || patternLength - patternIndex > stringLength - strIndex) {
39            return false;
40        }
41        // Get the current character from the pattern.
42        char currentPatternChar = pattern.charAt(patternIndex);
43        // Try all possible substrings of str starting at strIndex.
44        for (int end = strIndex + 1; end <= stringLength; ++end) {
45            String currentSubstring = str.substring(strIndex, end);
46            // Check if the current pattern character is already mapped to this substring.
47            if (patternMapping.getOrDefault(currentPatternChar, "").equals(currentSubstring)) {
48                if (depthFirstSearch(patternIndex + 1, end)) {
49                    return true;
50                }
51            } else if (!patternMapping.containsKey(currentPatternChar) && !visited.contains(currentSubstring)) {
52                // If the current pattern character is not mapped and the current substring has not been visited, try this new pattern-substring pair.
53                patternMapping.put(currentPatternChar, currentSubstring);
54                visited.add(currentSubstring);
55                if (depthFirstSearch(patternIndex + 1, end)) {
56                    return true;
57                }
58                // Backtrack and try different mappings for the current pattern character.
59                visited.remove(currentSubstring);
60                patternMapping.remove(currentPatternChar);
61            }
62        }
63        // If no valid mapping was found, return false.
64        return false;
65    }
66}
67
1class Solution {
2public:
3    // Main function to check if the pattern matches the string
4    bool wordPatternMatch(string pattern, string s) {
5        unordered_set<string> visited; // Holds unique mappings
6        unordered_map<char, string> dict; // Maps pattern chars to strings
7        // Start recursive depth-first search for pattern matching
8        return dfs(0, 0, pattern, s, visited, dict);
9    }
10
11    // Helper function to perform a depth-first search
12    bool dfs(int patternIndex, int strIndex, string& pattern, string& str, 
13             unordered_set<string>& visited, unordered_map<char, string>& dict) {
14        int patternSize = pattern.size(), strSize = str.size();
15        // If both pattern and string indices are at the end, we have a match
16        if (patternIndex == patternSize && strIndex == strSize) return true;
17        // If one of them is at the end or if there aren't enough characters 
18        // left in str for the remaining pattern, there's no match
19        if (patternIndex == patternSize || strIndex == strSize || patternSize - patternIndex > strSize - strIndex) return false;
20      
21        // Current pattern character
22        char currentChar = pattern[patternIndex];
23      
24        // Try every possible string partition
25        for (int k = strIndex + 1; k <= strSize; ++k) {
26            // Get a substring from the current str index up to k
27            string t = str.substr(strIndex, k - strIndex);
28            // If current pattern char is already associated with that substring
29            if (dict.count(currentChar) && dict[currentChar] == t) {
30                // Continue the search for the rest of the string and pattern
31                if (dfs(patternIndex + 1, k, pattern, str, visited, dict)) return true;
32            } 
33            // If current pattern char isn't associated yet and t is a new word
34            if (!dict.count(currentChar) && !visited.count(t)) {
35                // Create new associations and continue search
36                dict[currentChar] = t;
37                visited.insert(t);
38                if (dfs(patternIndex + 1, k, pattern, str, visited, dict)) return true;
39                // Backtracking: undo the association if it doesn't lead to a solution
40                visited.erase(t);
41                dict.erase(currentChar);
42            }
43        }
44        // If no partitioning leads to a solution, return false
45        return false;
46    }
47};
48
1// Importing Set and Map classes from ES6 for usage
2import { Set } from "typescript-collections";
3import { Map } from "typescript-collections";
4
5// Tracks unique mappings of strings to characters
6const visited: Set<string> = new Set();
7// Maps pattern characters to strings
8const dict: Map<string, string> = new Map();
9
10// Main function to check if the pattern matches the string
11function wordPatternMatch(pattern: string, s: string): boolean {
12    // Start recursive depth-first search for pattern matching
13    return dfs(0, 0, pattern, s);
14}
15
16// Helper function to perform a depth-first search
17function dfs(patternIndex: number, strIndex: number, pattern: string, str: string): boolean {
18    // The sizes of the pattern and the string
19    const patternSize: number = pattern.length;
20    const strSize: number = str.length;
21
22    // If both pattern and string indices are at the end, we have a match
23    if (patternIndex === patternSize && strIndex === strSize) return true;
24    // If one of them is at the end, or if there aren't enough characters 
25    // left in str to match the remaining pattern, there's no match
26    if (patternIndex === patternSize || strIndex === strSize || patternSize - patternIndex > strSize - strIndex) return false;
27  
28    // Current pattern character
29    const currentChar: string = pattern.charAt(patternIndex);
30  
31    // Attempt every possible partition of the string
32    for (let k: number = strIndex + 1; k <= strSize; k++) {
33        // Get a substring from the current str index up to k
34        const t: string = str.substring(strIndex, k);
35        // If current pattern character is already associated with that substring
36        if (dict.containsKey(currentChar) && dict.getValue(currentChar) === t) {
37            // Continue the search for the rest of the string and pattern
38            if (dfs(patternIndex + 1, k, pattern, str)) return true;
39        }
40        // If current pattern character isn't associated yet, and t is a new substring
41        if (!dict.containsKey(currentChar) && !visited.contains(t)) {
42            // Create new associations and continue search
43            dict.setValue(currentChar, t);
44            visited.add(t);
45            if (dfs(patternIndex + 1, k, pattern, str)) return true;
46            // Backtracking: undo the association if it doesn't lead to a solution
47            visited.remove(t);
48            dict.remove(currentChar);
49        }
50    }
51
52    // If no partitioning leads to a solution, return false
53    return false;
54}
55
Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

Time and Space Complexity

Time Complexity

The time complexity of the function is dependent on the number of recursive calls made by the dfs function. In each call, the function tries to map pattern[i] to a substring of s starting at index j. The for loop in dfs can run up to O(n) times for each call, where n is the size of string s.

In the worst case, the pattern can be bijectively mapped onto a prefix of s, leading to a situation where each character in pattern maps to a different substring of s. This means that there could be up to n levels in our recursion tree, each having n branches if we assume that the length of s is n.

Therefore, the worst-case time complexity is O(n^m), where m is the length of the pattern and n is the length of the string s. However, since the depth of the recursion is also restricted by the size of m with the condition n - j < m - i, the actual time complexity could potentially be lower, but the upper bound still holds as the worst-case scenario.

Space Complexity

The space complexity is influenced by the storage of the mappings (d) and the visited substrings (vis), in addition to the recursion call stack.

The maximum size of the dictionary d is bounded by the length of the pattern m, since at most each character in pattern can map to a unique substring of s. Therefore, the space taken by d is O(m).

The vis set can potentially contain all possible substrings of s that are mapped to pattern characters. In the worst case, this could result in O(n^2) space complexity since there can be n choices for the starting point and n choices for the ending point of the substring.

The recursion stack can go as deep as the number of characters in pattern, so the maximum depth is O(m).

Combining these considerations, the total space complexity becomes O(m + n^2), with n^2 usually dominating unless m is significantly larger than n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫