Solution Approach
Solution Overview
There are 3 main approaches to solve this problem:
- Dynamic Programming Approach - Complex approach
- Greedy Approach with Backtracking - Complex approach
- Recursive Approach with Memoization - Complex approach
Approach 1: Dynamic Programming Approach
The dynamic programming approach involves creating a 2D DP table where dp[i][j] represents whether the first i characters of the text match the first j characters of the pattern.
We fill this table incrementally, considering different cases based on the current characters in the text and pattern.
Algorithm:
- Create a 2D DP table of size (m+1) × (n+1), where m is the length of the text and n is the length of the pattern.
- Initialize dp[0][0] = true (empty pattern matches empty text).
- For patterns starting with '*', set dp[0][j] accordingly, as '*' can match an empty string.
- For each cell dp[i][j], consider the following cases:
- a. If pattern[j-1] is '?', it matches any single character, so dp[i][j] = dp[i-1][j-1].
- b. If pattern[j-1] is '*', it can match zero or more characters, so dp[i][j] = dp[i][j-1] || dp[i-1][j].
- c. If pattern[j-1] is a regular character, it must match the current character in the text, so dp[i][j] = (text[i-1] == pattern[j-1]) && dp[i-1][j-1].
- Return dp[m][n], which represents whether the entire text matches the entire pattern.
Time Complexity:
Where m is the length of the text and n is the length of the pattern. We fill in a table of size m × n, and each cell takes constant time to compute.
Space Complexity:
We need a 2D DP table of size (m+1) × (n+1) to store the intermediate results.
Approach 2: Greedy Approach with Backtracking
The greedy approach with backtracking tries to match the pattern character by character, with special handling for the '*' character. When we encounter a '*', we have multiple choices: match zero characters, match one character, match two characters, and so on.
We use a greedy strategy by initially trying to match as few characters as possible with '*', and then backtracking if necessary.
Algorithm:
- Initialize two pointers, i for the text and j for the pattern.
- Initialize variables to keep track of the last '*' position in the pattern and the corresponding position in the text.
- While i < length of text:
- a. If j < length of pattern and (pattern[j] is '?' or pattern[j] matches text[i]), advance both pointers.
- b. If j < length of pattern and pattern[j] is '*', record the position of '*' and the current position in the text, then advance only the pattern pointer.
- c. If we can't match the current characters but we've seen a '*' before, backtrack to the position after the last '*' in the pattern and advance the text pointer.
- d. If none of the above conditions are met, return false.
- Skip any remaining '*' characters in the pattern.
- Return true if we've reached the end of the pattern, false otherwise.
Time Complexity:
Where m is the length of the text and n is the length of the pattern. In the worst case, we might need to backtrack for each character in the text, leading to O(m × n) time complexity.
Space Complexity:
We only use a constant amount of extra space regardless of the input size.
Approach 3: Recursive Approach with Memoization
The recursive approach breaks down the problem by considering one character at a time from both the text and pattern. We handle different cases based on the current characters and use memoization to avoid redundant calculations.
This approach is similar to the dynamic programming approach but uses recursion instead of iteration.
Algorithm:
- Create a recursive function that takes the current positions in the text and pattern.
- Use memoization to store results of subproblems to avoid redundant calculations.
- Base case: If we've reached the end of the pattern, return true if we've also reached the end of the text.
- If the current pattern character is '?', it matches any single character, so move to the next characters in both strings.
- If the current pattern character is '*', we have two choices:
- a. Skip the '*' (match zero characters).
- b. Match the current text character with the '*' and continue matching.
- If the current characters match, move to the next characters in both strings.
- Return false if none of the above conditions are met.
Time Complexity:
Where m is the length of the text and n is the length of the pattern. With memoization, we solve each subproblem only once, and there are m × n possible subproblems.
Space Complexity:
We need O(m × n) space for the memoization table to store results for all possible subproblems. The recursion stack also uses O(m + n) space in the worst case.
Pseudocode
1234567891011121314151617181920212223242526272829function isMatch(text, pattern): m = length of text n = length of pattern // Create a DP table dp = 2D array of size (m+1) × (n+1) initialized with false // Empty pattern matches empty text dp[0][0] = true // Handle patterns starting with '*' for j from 1 to n: if pattern[j-1] == '*': dp[0][j] = dp[0][j-1] // Fill the DP table for i from 1 to m: for j from 1 to n: if pattern[j-1] == '?': // '?' matches any single character dp[i][j] = dp[i-1][j-1] else if pattern[j-1] == '*': // '*' can match zero or more characters dp[i][j] = dp[i][j-1] || dp[i-1][j] else: // Regular character must match dp[i][j] = (text[i-1] == pattern[j-1]) && dp[i-1][j-1] return dp[m][n]String Problems
Learning Objective
Understand different approaches to solve the wildcard pattern matcher problem and analyze their efficiency.
Solution Approaches
Approach 1: Dynamic Programming Approach
The dynamic programming approach involves creating a 2D DP table where dp[i][j] represents whether the first i characters of the text match the first j characters of the pattern.
We fill this table incrementally, considering different cases based on the current characters in the text and pattern.
Algorithm:
- Create a 2D DP table of size (m+1) × (n+1), where m is the length of the text and n is the length of the pattern.
- Initialize dp[0][0] = true (empty pattern matches empty text).
- For patterns starting with '*', set dp[0][j] accordingly, as '*' can match an empty string.
- For each cell dp[i][j], consider the following cases:
- a. If pattern[j-1] is '?', it matches any single character, so dp[i][j] = dp[i-1][j-1].
- b. If pattern[j-1] is '*', it can match zero or more characters, so dp[i][j] = dp[i][j-1] || dp[i-1][j].
- c. If pattern[j-1] is a regular character, it must match the current character in the text, so dp[i][j] = (text[i-1] == pattern[j-1]) && dp[i-1][j-1].
- Return dp[m][n], which represents whether the entire text matches the entire pattern.
Approach 2: Greedy Approach with Backtracking
The greedy approach with backtracking tries to match the pattern character by character, with special handling for the '*' character. When we encounter a '*', we have multiple choices: match zero characters, match one character, match two characters, and so on.
We use a greedy strategy by initially trying to match as few characters as possible with '*', and then backtracking if necessary.
Algorithm:
- Initialize two pointers, i for the text and j for the pattern.
- Initialize variables to keep track of the last '*' position in the pattern and the corresponding position in the text.
- While i < length of text:
- a. If j < length of pattern and (pattern[j] is '?' or pattern[j] matches text[i]), advance both pointers.
- b. If j < length of pattern and pattern[j] is '*', record the position of '*' and the current position in the text, then advance only the pattern pointer.
- c. If we can't match the current characters but we've seen a '*' before, backtrack to the position after the last '*' in the pattern and advance the text pointer.
- d. If none of the above conditions are met, return false.
- Skip any remaining '*' characters in the pattern.
- Return true if we've reached the end of the pattern, false otherwise.
Approach 3: Recursive Approach with Memoization
The recursive approach breaks down the problem by considering one character at a time from both the text and pattern. We handle different cases based on the current characters and use memoization to avoid redundant calculations.
This approach is similar to the dynamic programming approach but uses recursion instead of iteration.
Algorithm:
- Create a recursive function that takes the current positions in the text and pattern.
- Use memoization to store results of subproblems to avoid redundant calculations.
- Base case: If we've reached the end of the pattern, return true if we've also reached the end of the text.
- If the current pattern character is '?', it matches any single character, so move to the next characters in both strings.
- If the current pattern character is '*', we have two choices:
- a. Skip the '*' (match zero characters).
- b. Match the current text character with the '*' and continue matching.
- If the current characters match, move to the next characters in both strings.
- Return false if none of the above conditions are met.
Complexity Analysis
Dynamic Programming Approach Approach
Time Complexity
Where m is the length of the text and n is the length of the pattern. We fill in a table of size m × n, and each cell takes constant time to compute.
Space Complexity
We need a 2D DP table of size (m+1) × (n+1) to store the intermediate results.
Greedy Approach with Backtracking Approach
Time Complexity
Where m is the length of the text and n is the length of the pattern. In the worst case, we might need to backtrack for each character in the text, leading to O(m × n) time complexity.
Space Complexity
We only use a constant amount of extra space regardless of the input size.
Recursive Approach with Memoization Approach
Time Complexity
Where m is the length of the text and n is the length of the pattern. With memoization, we solve each subproblem only once, and there are m × n possible subproblems.
Space Complexity
We need O(m × n) space for the memoization table to store results for all possible subproblems. The recursion stack also uses O(m + n) space in the worst case.
Pseudocode
Dynamic Programming Approach Approach
1234567891011121314151617181920212223242526272829function isMatch(text, pattern): m = length of text n = length of pattern // Create a DP table dp = 2D array of size (m+1) × (n+1) initialized with false // Empty pattern matches empty text dp[0][0] = true // Handle patterns starting with '*' for j from 1 to n: if pattern[j-1] == '*': dp[0][j] = dp[0][j-1] // Fill the DP table for i from 1 to m: for j from 1 to n: if pattern[j-1] == '?': // '?' matches any single character dp[i][j] = dp[i-1][j-1] else if pattern[j-1] == '*': // '*' can match zero or more characters dp[i][j] = dp[i][j-1] || dp[i-1][j] else: // Regular character must match dp[i][j] = (text[i-1] == pattern[j-1]) && dp[i-1][j-1] return dp[m][n]Greedy Approach with Backtracking Approach
123456789101112131415161718192021222324252627282930313233function isMatch(text, pattern): m = length of text n = length of pattern i = 0 // pointer for text j = 0 // pointer for pattern starIdx = -1 // position of last '*' in pattern match = 0 // position in text corresponding to last '*' while i < m: // If current characters match or pattern has '?' if j < n && (pattern[j] == '?' || pattern[j] == text[i]): i++ j++ // If pattern has '*' else if j < n && pattern[j] == '*': starIdx = j match = i j++ // If we've seen a '*' before, backtrack else if starIdx != -1: j = starIdx + 1 match++ i = match // If none of the above conditions are met, no match else: return false // Skip any remaining '*' characters in pattern while j < n && pattern[j] == '*': j++ // Return true if we've reached the end of the pattern return j == n