Regular Expression Matching
Problem
Given a string s and a pattern p, return true if s matches p, where p supports '.' matching any single character and '*' matching zero or more of the preceding element.
- 0 ≤ s.length ≤ 20
- 0 ≤ p.length ≤ 30
- s contains only lowercase English letters
- p contains only lowercase English letters, '.' and '*'
- It is guaranteed for each appearance of '*', there will be a valid preceding character
Example
s = "aab", p = "c*a*b"trueThe pattern 'c*' can match zero 'c's, so it is ignored. Then 'a*' matches two 'a's in 'aab'. Finally, 'b' matches the last character 'b'. Thus, the entire string matches the pattern.
Approach
Straightforward Solution
A naive recursive solution tries all possible ways to match the pattern against the string, leading to exponential time complexity due to repeated computations and branching on '*'. This approach is infeasible for longer inputs.
Core Observation
Matching a string against a pattern with '.' and '*' can be broken down into subproblems defined by the current indices in s and p. The '*' operator introduces branching: it can either match zero occurrences of the preceding element or consume one character if it matches. This creates overlapping subproblems that can be cached.
Path to Optimal
The key recognition signals are 'pattern matching with wildcards', 'zero or more repetitions', and 'full string coverage'. These indicate Dynamic Programming because the problem breaks down into overlapping subproblems defined by indices in s and p. Memoization avoids redundant computations by caching results for each (i, j) state. The recursive function explores two cases when encountering '*': skipping the '*' and its preceding character, or consuming one matching character and continuing with the same pattern index.
Optimal Approach
Use a top-down recursive DP with memoization keyed by (i, j), representing the current indices in s and p. For each state, check if the next character in p is '*'. If so, recursively check two branches: skipping the '*' and its preceding character, or if the current characters match, consuming one character from s and continuing with the same pattern index. If no '*', match the current characters and recurse forward. Cache all results to ensure each state is computed once, yielding polynomial time complexity.
Time
O(m * n)
There are at most m * n unique states, where m and n are the lengths of s and p respectively. Each state is computed once and cached, and each computation does O(1) work plus recursive calls to other states.
Space
O(m * n)
The memoization dictionary stores results for each (i, j) state, requiring O(m * n) auxiliary space. The recursion stack depth is at most O(m + n), which is bounded by O(m * n).
Pattern Spotlight
Dynamic Programming (Top-Down Memoization for Pattern Matching)
When a problem involves matching with wildcards and repetition operators, model the problem as a state machine over indices and cache results for each state to avoid exponential recomputation caused by branching.
Solution
| 1 | class Solution:
|
| 2 | def isMatch(self, s: str, p: str) -> bool:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, j):
|
| 6 | if (i, j) in memo:
|
| 7 | return memo[(i, j)]
|
| 8 | if j == len(p):
|
| 9 | return i == len(s)
|
| 10 |
|
| 11 | first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
|
| 12 |
|
| 13 | if (j + 1) < len(p) and p[j + 1] == '*':
|
| 14 | res = (dp(i, j + 2) or
|
| 15 | (first_match and dp(i + 1, j)))
|
| 16 | else:
|
| 17 | res = first_match and dp(i + 1, j + 1)
|
| 18 |
|
| 19 | memo[(i, j)] = res
|
| 20 | return res
|
| 21 |
|
| 22 | return dp(0, 0) |
Step-by-Step Solution
Cache Recursive Results to Avoid Redundant Computation
| 3 | memo = {}
|
| 5 | def dp(i, j):
|
| 6 | if (i, j) in memo:
|
| 7 | return memo[(i, j)]
|
Objective
To store the results of subproblems identified by indices (i, j) in a memo dictionary to prevent repeated work.
Key Insight
The recursive matching function explores overlapping subproblems due to the '*' operator's branching. By caching the boolean result for each (i, j) pair, the algorithm avoids exponential recomputation, ensuring each state is solved once. This memoization transforms the naive recursion into efficient dynamic programming.
Interview Quick-Check
Core Logic
Memoization keyed by (i, j) ensures that each unique substring and subpattern pair is evaluated once, preventing exponential blowup.
Common Pitfalls & Bugs
Failing to memoize leads to repeated exploration of the same states, causing timeouts on larger inputs.
Handle Base Case When Pattern is Exhausted
| 8 | if j == len(p):
|
| 9 | return i == len(s)
|
Objective
To determine if the entire string has been matched when the pattern is fully consumed.
Key Insight
If the pattern index j reaches the end, the string matches only if the string index i is also at the end. This base case terminates recursion and defines the boundary condition for the DP states.
Interview Quick-Check
Core Logic
When the pattern is exhausted, the match is successful only if the string is also fully consumed.
State & Boundaries
This base case prevents out-of-bounds errors and correctly signals completion of matching.
Check Current Character Match with Support for Wildcard '.'
| 11 | first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
|
Objective
To verify if the current characters in s and p match, considering '.' as a wildcard.
Key Insight
A match occurs if the current character in s equals the current character in p, or if p[j] is '.', which matches any single character. This check is fundamental to deciding how to proceed with recursion.
Interview Quick-Check
Core Logic
The first_match boolean captures whether the current characters align, enabling correct branching for '*' and direct matches.
Common Pitfalls & Bugs
Not checking that i < len(s) before accessing s[i] can cause index errors.
Branch on '*' Operator to Explore Zero or More Matches
| 13 | if (j + 1) < len(p) and p[j + 1] == '*':
|
| 14 | res = (dp(i, j + 2) or
|
| 15 | (first_match and dp(i + 1, j)))
|
Objective
To handle the '*' operator by recursively exploring skipping it or consuming matching characters.
Key Insight
When the next character in p is '*', two possibilities arise: skip the '*' and its preceding character (zero occurrences), or if the current characters match, consume one character from s and continue matching with the same pattern index (one or more occurrences). This branching captures the semantics of '*'.
Interview Quick-Check
Core Logic
The recursive call dp(i, j+2) skips the '*' and preceding char, while dp(i+1, j) consumes one matching character, enabling repetition.
Common Pitfalls & Bugs
Forgetting to check that j+1 < len(p) before accessing p[j+1] can cause index errors.
Advance Both String and Pattern Indices on Direct Match
| 16 | else:
|
| 17 | res = first_match and dp(i + 1, j + 1)
|
Objective
To move forward in both s and p when the current characters match and no '*' follows.
Key Insight
If the next character in p is not '*', the match depends on the current characters matching and the remainder of the strings matching recursively. This linear progression is the base case for non-repetitive pattern characters.
Interview Quick-Check
Core Logic
The recursive call dp(i+1, j+1) advances both indices when characters match and no '*' follows.
Memoize and Return the Computed Result for Current State
| 19 | memo[(i, j)] = res
|
| 20 | return res
|
Objective
To store the computed boolean result for the current (i, j) state and return it.
Key Insight
Memoizing the result ensures that future calls with the same indices return instantly, preventing redundant computation and enabling efficient DP.
Interview Quick-Check
Core Logic
Storing the result in memo[(i, j)] caches the answer for this subproblem, enabling O(m*n) time complexity.
Initiate Recursive Matching from Start of Strings
| 22 | return dp(0, 0) |
Objective
To start the recursive matching process from the beginning of s and p.
Key Insight
Calling dp(0, 0) triggers the entire top-down DP recursion, exploring all subproblems and returning the final match result.
Interview Quick-Check
Core Logic
Starting at indices (0, 0) covers the entire strings and initiates the recursive exploration.
Line Analysis
This solution has 8 Critical lines interviewers watch for.
if (i, j) in memo:Check if the current state (i, j) has been computed before.
This lookup prevents redundant work by returning cached results, a cornerstone of top-down DP.
return memo[(i, j)]Return the cached result for the current state if available.
Returning cached results immediately prunes the recursion tree, ensuring polynomial time complexity.
memo = {}Initialize a memoization dictionary to cache subproblem results.
Memoization is essential to avoid exponential recomputation by storing results of each (i, j) state, enabling efficient dynamic programming.
return i == len(s)Return true if both string and pattern are fully matched; otherwise false.
Matching is successful only if both s and p are fully consumed, ensuring complete coverage.
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')Determine if current characters match or if pattern has a wildcard '.' at j.
This boolean captures the fundamental matching condition for the current character, enabling correct branching for '*' and direct matches.
if (j + 1) < len(p) and p[j + 1] == '*':Check if the next character in pattern is '*' to handle repetition.
Identifying '*' triggers branching logic to explore zero or more occurrences, which is the core complexity of regex matching.
(first_match and dp(i + 1, j)))Recursively check the case where '*' matches one or more occurrences if first characters match.
Consuming one character from s while keeping pattern index models repetition, enabling matching of multiple characters.
memo[(i, j)] = resStore the computed result for the current state in the memo dictionary.
Caching results is essential to prevent recomputation and achieve polynomial time complexity.
if j == len(p):Check if the pattern index j has reached the end.
This base case determines if the entire pattern has been consumed, a critical boundary condition for correctness.
res = (dp(i, j + 2) orRecursively check the case where '*' matches zero occurrences by skipping it.
Skipping '*' and its preceding character models zero repetition, a critical branch in the matching logic.
else:Handle the case where no '*' follows: match current characters and recurse forward.
Linear progression when no repetition operator is present ensures correct matching of single characters.
res = first_match and dp(i + 1, j + 1)Return the result of matching current characters and the rest of the strings.
Combining current match with recursive result ensures correctness of the overall matching process.
return resReturn the cached or newly computed result for the current state.
Returning the memoized result completes the recursive call, enabling correct propagation of match results.
def dp(i, j):Define the recursive function dp that takes indices i and j for s and p respectively.
Encapsulating the matching logic in a recursive function with state parameters allows systematic exploration of all subproblems with memoization.
return dp(0, 0)Start the recursive matching process from the beginning of s and p.
This call triggers the entire DP recursion, exploring all subproblems and returning the final answer.
Test Your Understanding
Why does memoizing the results of subproblems defined by indices (i, j) prevent exponential time complexity?
Because the problem's branching due to '*' can revisit the same (i, j) state multiple times, caching ensures each state is computed once, eliminating redundant recursive calls and reducing the complexity from exponential to polynomial.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Regular Expression Matching from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Regular Expression Matching drill