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.

Flowchart Walkthrough

Let's analyze LeetCode 291. Word Pattern II using the Flowchart. Here's the step-by-step process:

Is it a graph?

  • No: This problem does not involve a typical graph structure with nodes interconnected by edges.

Need to solve for kth smallest/largest?

  • No: The problem is not about finding kth smallest or largest elements, but about finding a mapping from characters to strings that match a given pattern.

Involves Linked Lists?

  • No: This problem does not involve manipulating or traversing linked lists.

Does the problem have small constraints?

  • Yes: The problem involves matching a pattern and a string, potentially with small constraints given that the pattern length is generally small, facilitating the feasibility of trying out different mappings.

Brute force / Backtracking?

  • Yes: The problem requires exploring all potential mappings from pattern characters to parts of the string, checking each mapping to see if it fits the pattern. This exhaustive search is typically implemented using backtracking.

Conclusion: Based on the analysis using the flowchart, backtracking is advised for solving LeetCode 291. Word Pattern II, as it involves trying multiple mappings and seeing which ones correctly map the entire pattern to the string under the defined constraints.

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.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More