Approach Summary
dp[i][j] = true if s[0..i) matches p[0..j). Handle "." (matches any) and "*" (matches zero or more of the preceding char).
How to Recognize This Pattern
- Pattern with "." and "*"
- "*" means zero or more: dp[i][j] = dp[i][j-2] (zero) OR match+dp[i-1][j] (more)
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
String Dynamic Programming Recursion