291. Word Pattern II
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:
-
Depth-First Search (DFS) with Backtracking:
- The
dfs
function is a recursive function that keeps track of the current positioni
in thepattern
and the current positionj
in the strings
. - If
i
equals the length ofpattern
(m
) andj
equals the length ofs
(n
), it means we have successfully mapped the entire pattern to the strings
, and we returnTrue
. - If either
i
equalsm
orj
equalsn
before the other, or if there aren't enough characters left ins
to match the remaining pattern (n - j < m - i
), we returnFalse
as it signifies that the current mapping does not covers
orpattern
correctly.
- The
-
Attempt to Match Substrings:
- The
dfs
function iterates over the substring ofs
starting from indexj
and ending at various pointsk
within the string. This loop essentially tries to map the current pattern character to various lengths of substrings ins
. - We extract the current substring of
s
from indexj
tok
and store it in a variablet
. - If the current pattern character at index
i
already has a mapping in the dictionaryd
and it is equal tot
, we recursively calldfs
for the next character in the pattern and the next part of the string. If this returnsTrue
, then the current mapping is part of a solution, and we propagate this success back up the recursion chain.
- The
-
Adding New Mappings:
- If the current pattern character at index
i
is not yet mapped in the dictionaryd
and the substringt
is not already used (checked using setvis
), we add the mappingpattern[i] -> t
tod
and addt
tovis
. - We then recurse to see if this new mapping could lead to a solution.
- Whether the recursive call returns
True
orFalse
, we then backtrack by removing the current mapping fromd
andt
fromvis
, allowing the next iteration to try a different mapping for the same pattern character.
- If the current pattern character at index
-
Data Structures:
- A dictionary
d
is used to keep track of the current mapping from pattern characters to substrings ins
. - A set
vis
is used to keep track of the substrings ofs
that have already been mapped to some pattern characters. This helps ensure the bijective nature of the mapping.
- A dictionary
-
Initiating the Recursive Search:
- Before starting the backtracking process, we initialize the variables
m
andn
to hold the lengths ofpattern
ands
, respectively. The dictionaryd
and the setvis
are initialized to be empty. - The
dfs
function is then initiated withi
andj
both set to 0, which signifies the start ofpattern
ands
.
- Before starting the backtracking process, we initialize the variables
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 EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Consider the pattern
"aba" and the string s
"catdogcat".
-
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'.
- We examine the first character in the
-
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.
- On the first attempt, we associate 'a' with 'c' and then recurse to the next character in the
-
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.
-
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 returnTrue
.
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.
In a binary min heap, the minimum element can be found in:
Recommended Readings
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 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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.