Core Insight A table exposes how two changing prefixes or positions depend on smaller cases.
Common Pitfall Initialize the first row and column before using neighboring cells.
Description
Implement regular expression matching with . and *.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m·n)
Tags
stringdynamic-programmingrecursion
Implementation Plan Translate the invariant into these small, testable moves.
- Define the row and column meaning.
- Initialize base cases.
- Fill cells in dependency order.
- Read the answer from the target cell.
def isMatch(s, p):
cache = {}
def dfs(i, j):
if (i, j) in cache:
return cache[(i, j)]
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == ".")
if (j + 1) < len(p) and p[j + 1] == "*":
cache[(i, j)] = (dfs(i, j + 2) or
(match and dfs(i + 1, j)))
return cache[(i, j)]
if match:
cache[(i, j)] = dfs(i + 1, j + 1)
return cache[(i, j)]
cache[(i, j)] = False
return False
return dfs(0, 0)