Solution Approach
Solution Overview
There are 2 main approaches to solve this problem:
- Recursive Approach with Memoization - Complex approach
- Dynamic Programming Approach - Complex approach
Approach 1: 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.
The key insight is to handle the '*' character separately. When we encounter a '*', we have two choices:
- Ignore the character and its preceding element (match zero occurrences)
- Match the current character in the text with the preceding element in the pattern and continue matching
Algorithm:
- Create a recursive function that takes the current positions in the text and pattern.
- 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 next character in the pattern is followed by '*', we have two options:
- a. Skip the pattern character and the '*' (match zero occurrences).
- b. If the current characters match, try matching the current text character with the pattern character and continue.
- If the current characters match (either exact match or '.'), move to the next characters in both strings.
- Use memoization to store results of subproblems to avoid redundant calculations.
- 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.
Approach 2: Dynamic Programming Approach
We can solve this problem using a bottom-up dynamic programming approach. 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.
The key is to build the table incrementally, starting from empty strings and working our way up to the full strings.
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 like 'a*', 'b*', etc., which can match empty strings, set dp[0][j] accordingly.
- For each cell dp[i][j], consider the following cases:
- a. If pattern[j-1] is '*', we have two options:
- i. Ignore the pattern character and its preceding element (dp[i][j-2]).
- ii. If the current text character matches the preceding pattern character, use the result from dp[i-1][j].
- b. If the current characters match (either exact match or '.'), use the result from 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.
Pseudocode
123456789101112131415161718192021222324252627282930function isMatch(text, pattern): // Create a memoization map memo = {} function match(i, j): // Check if we've already computed this result if (i, j) in memo: return memo[(i, j)] // Base case: if we've reached the end of the pattern if j == length of pattern: return i == length of text // Check if the current characters match firstMatch = i < length of text and (pattern[j] == text[i] or pattern[j] == '.') // If the next character is '*' if j + 1 < length of pattern and pattern[j + 1] == '*': // Either skip the pattern character and '*' (match zero occurrences) // or match the current character and continue with the same pattern result = match(i, j + 2) or (firstMatch and match(i + 1, j)) else: // If the current characters match, move to the next characters result = firstMatch and match(i + 1, j + 1) // Store the result in the memoization map memo[(i, j)] = result return result return match(0, 0)String Problems
Learning Objective
Understand different approaches to solve the regular expression matcher problem and analyze their efficiency.
Solution Approaches
Approach 1: 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.
The key insight is to handle the '*' character separately. When we encounter a '*', we have two choices:
- Ignore the character and its preceding element (match zero occurrences)
- Match the current character in the text with the preceding element in the pattern and continue matching
Algorithm:
- Create a recursive function that takes the current positions in the text and pattern.
- 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 next character in the pattern is followed by '*', we have two options:
- a. Skip the pattern character and the '*' (match zero occurrences).
- b. If the current characters match, try matching the current text character with the pattern character and continue.
- If the current characters match (either exact match or '.'), move to the next characters in both strings.
- Use memoization to store results of subproblems to avoid redundant calculations.
- Return false if none of the above conditions are met.
Approach 2: Dynamic Programming Approach
We can solve this problem using a bottom-up dynamic programming approach. 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.
The key is to build the table incrementally, starting from empty strings and working our way up to the full strings.
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 like 'a*', 'b*', etc., which can match empty strings, set dp[0][j] accordingly.
- For each cell dp[i][j], consider the following cases:
- a. If pattern[j-1] is '*', we have two options:
- i. Ignore the pattern character and its preceding element (dp[i][j-2]).
- ii. If the current text character matches the preceding pattern character, use the result from dp[i-1][j].
- b. If the current characters match (either exact match or '.'), use the result from dp[i-1][j-1].
- Return dp[m][n], which represents whether the entire text matches the entire pattern.
Complexity Analysis
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.
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.
Pseudocode
Recursive Approach with Memoization Approach
123456789101112131415161718192021222324252627282930function isMatch(text, pattern): // Create a memoization map memo = {} function match(i, j): // Check if we've already computed this result if (i, j) in memo: return memo[(i, j)] // Base case: if we've reached the end of the pattern if j == length of pattern: return i == length of text // Check if the current characters match firstMatch = i < length of text and (pattern[j] == text[i] or pattern[j] == '.') // If the next character is '*' if j + 1 < length of pattern and pattern[j + 1] == '*': // Either skip the pattern character and '*' (match zero occurrences) // or match the current character and continue with the same pattern result = match(i, j + 2) or (firstMatch and match(i + 1, j)) else: // If the current characters match, move to the next characters result = firstMatch and match(i + 1, j + 1) // Store the result in the memoization map memo[(i, j)] = result return result return match(0, 0)Dynamic Programming Approach Approach
1234567891011121314151617181920212223242526272829303132function 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 like a*, b*, etc. which can match empty string for j from 1 to n: if pattern[j-1] == '*': dp[0][j] = dp[0][j-2] // Fill the DP table for i from 1 to m: for j from 1 to n: if pattern[j-1] == '*': // Either ignore the pattern character and its preceding element dp[i][j] = dp[i][j-2] // Or if the current text character matches the preceding pattern character, // use the result from dp[i-1][j] if pattern[j-2] == '.' or pattern[j-2] == text[i-1]: dp[i][j] = dp[i][j] or dp[i-1][j] else: // If the current characters match, use the result from dp[i-1][j-1] if pattern[j-1] == '.' or pattern[j-1] == text[i-1]: dp[i][j] = dp[i-1][j-1] return dp[m][n]