Solution Approach
Solution Overview
There are 2 main approaches to solve this problem:
- Recursive Approach - Complex approach
- Dynamic Programming Approach - Complex approach
Approach 1: Recursive Approach
We can solve this problem using recursion by breaking it down into smaller subproblems. At each step, we consider the current characters in both the text and pattern and make decisions based on what we encounter.
The key insight is to handle the '*' wildcard specially, as it can match zero or more characters. When we encounter a '*', we have two choices: either use it to match zero characters and move only in the pattern, or use it to match one or more characters by moving in the text.
Algorithm:
- Define a recursive function isMatch(text, pattern, i, j) where i and j are the current positions in the text and pattern.
- Base case: If we've reached the end of both text and pattern, return true.
- Base case: If we've reached the end of the pattern but not the text, return false.
- Base case: If we've reached the end of the text but not the pattern, return true only if all remaining characters in the pattern are '*'.
- If the current pattern character is '*':
- - Try matching zero characters: recursively call isMatch(text, pattern, i, j+1)
- - Try matching one or more characters: recursively call isMatch(text, pattern, i+1, j) if i < text.length
- - Return true if either of these recursive calls returns true.
- If the current pattern character is '?' or it matches the current text character:
- - Recursively call isMatch(text, pattern, i+1, j+1)
- Otherwise, return false.
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 explore all possible combinations of matching.
Space Complexity:
for the recursion stack. The maximum depth of recursion is bounded by the sum of the lengths of the text and pattern.
Approach 2: Dynamic Programming Approach
To optimize the recursive solution, we can use dynamic programming to avoid redundant calculations. We'll create 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.
Algorithm:
- Create a 2D boolean array dp of size (text.length+1) × (pattern.length+1).
- Initialize dp[0][0] = true (empty text matches empty pattern).
- For j from 1 to pattern.length:
- - If pattern[j-1] is '*', set dp[0][j] = dp[0][j-1] (empty text can match pattern with '*').
- For i from 1 to text.length and j from 1 to pattern.length:
- - If pattern[j-1] is '*':
- * dp[i][j] = dp[i][j-1] (match zero characters) || dp[i-1][j] (match one or more characters)
- - If pattern[j-1] is '?' or pattern[j-1] equals text[i-1]:
- * dp[i][j] = dp[i-1][j-1]
- - Otherwise, dp[i][j] = false
- Return dp[text.length][pattern.length].
Time Complexity:
where m is the length of the text and n is the length of the pattern. We fill a 2D table of size m×n.
Space Complexity:
for the DP table. We need to store the result for each combination of text and pattern positions.
Pseudocode
1234567891011121314151617181920212223242526272829function isMatch(text, pattern): return recursiveMatch(text, pattern, 0, 0) function recursiveMatch(text, pattern, i, j): // Base cases if j == pattern.length: return i == text.length if i == text.length: // Remaining pattern must be all '*' for k from j to pattern.length - 1: if pattern[k] != '*': return false return true // Current character in pattern if pattern[j] == '*': // Match zero characters if recursiveMatch(text, pattern, i, j+1): return true // Match one or more characters return recursiveMatch(text, pattern, i+1, j) // Match single character if pattern[j] == '?' or pattern[j] == text[i]: return recursiveMatch(text, pattern, i+1, j+1) return falseString Problems
Learning Objective
Understand different approaches to solve the email filter system problem and analyze their efficiency.
Solution Approaches
Approach 1: Recursive Approach
We can solve this problem using recursion by breaking it down into smaller subproblems. At each step, we consider the current characters in both the text and pattern and make decisions based on what we encounter.
The key insight is to handle the '*' wildcard specially, as it can match zero or more characters. When we encounter a '*', we have two choices: either use it to match zero characters and move only in the pattern, or use it to match one or more characters by moving in the text.
Algorithm:
- Define a recursive function isMatch(text, pattern, i, j) where i and j are the current positions in the text and pattern.
- Base case: If we've reached the end of both text and pattern, return true.
- Base case: If we've reached the end of the pattern but not the text, return false.
- Base case: If we've reached the end of the text but not the pattern, return true only if all remaining characters in the pattern are '*'.
- If the current pattern character is '*':
- - Try matching zero characters: recursively call isMatch(text, pattern, i, j+1)
- - Try matching one or more characters: recursively call isMatch(text, pattern, i+1, j) if i < text.length
- - Return true if either of these recursive calls returns true.
- If the current pattern character is '?' or it matches the current text character:
- - Recursively call isMatch(text, pattern, i+1, j+1)
- Otherwise, return false.
Approach 2: Dynamic Programming Approach
To optimize the recursive solution, we can use dynamic programming to avoid redundant calculations. We'll create 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.
Algorithm:
- Create a 2D boolean array dp of size (text.length+1) × (pattern.length+1).
- Initialize dp[0][0] = true (empty text matches empty pattern).
- For j from 1 to pattern.length:
- - If pattern[j-1] is '*', set dp[0][j] = dp[0][j-1] (empty text can match pattern with '*').
- For i from 1 to text.length and j from 1 to pattern.length:
- - If pattern[j-1] is '*':
- * dp[i][j] = dp[i][j-1] (match zero characters) || dp[i-1][j] (match one or more characters)
- - If pattern[j-1] is '?' or pattern[j-1] equals text[i-1]:
- * dp[i][j] = dp[i-1][j-1]
- - Otherwise, dp[i][j] = false
- Return dp[text.length][pattern.length].
Complexity Analysis
Recursive Approach 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 explore all possible combinations of matching.
Space Complexity
for the recursion stack. The maximum depth of recursion is bounded by the sum of the lengths of the text and pattern.
Dynamic Programming Approach Approach
Time Complexity
where m is the length of the text and n is the length of the pattern. We fill a 2D table of size m×n.
Space Complexity
for the DP table. We need to store the result for each combination of text and pattern positions.
Comparison:
The recursive approach is more intuitive but can be very inefficient for large inputs due to redundant calculations. The dynamic programming approach solves this by storing intermediate results, making it much more efficient with a time complexity of O(m×n) instead of O(2^(m+n)). For the email filtering system where performance is critical, the DP approach is strongly preferred.
Pseudocode
Recursive Approach Approach
1234567891011121314151617181920212223242526272829function isMatch(text, pattern): return recursiveMatch(text, pattern, 0, 0) function recursiveMatch(text, pattern, i, j): // Base cases if j == pattern.length: return i == text.length if i == text.length: // Remaining pattern must be all '*' for k from j to pattern.length - 1: if pattern[k] != '*': return false return true // Current character in pattern if pattern[j] == '*': // Match zero characters if recursiveMatch(text, pattern, i, j+1): return true // Match one or more characters return recursiveMatch(text, pattern, i+1, j) // Match single character if pattern[j] == '?' or pattern[j] == text[i]: return recursiveMatch(text, pattern, i+1, j+1) return falseDynamic Programming Approach Approach
12345678910111213141516171819202122232425262728function isMatch(text, pattern): m = text.length n = pattern.length // Create DP table dp = new boolean[m+1][n+1] // Empty text matches empty pattern dp[0][0] = true // Empty text can match pattern 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] == '*': // Match zero characters or one or more characters dp[i][j] = dp[i][j-1] || dp[i-1][j] else if pattern[j-1] == '?' or pattern[j-1] == text[i-1]: // Match single character dp[i][j] = dp[i-1][j-1] else: dp[i][j] = false return dp[m][n]