TL;DR
Prefix-matching DP: dp[i][j] = does s[:i] match p[:j], with a special * transition that means “zero copies or one-more copy” — O(len(s)·len(p)) time, O(len(p)) space with two rolling rows.
Approach 1 — Brute force recursion
Match from the front. A * at p[j+1] branches into “use zero copies” (skip p[j]p[j+1]) or “consume one character of s and stay on the same pattern”.
def isMatch(s: str, p: str) -> bool:
def match(i: int, j: int) -> bool:
if j == len(p):
return i == len(s)
first = i < len(s) and (p[j] == '.' or p[j] == s[i])
if j + 1 < len(p) and p[j + 1] == '*':
return match(i, j + 2) or (first and match(i + 1, j))
return first and match(i + 1, j + 1)
return match(0, 0)
Complexity: exponential. A * repeatedly forks into zero/one-more, and the same (i, j) pair is recomputed along many branches. Tracing s = "aa", p = "a*" shows the branching and the repeated subproblems:
graph TD
A["match(0,0)"] --> B["match(0,2)"]
A --> C["match(1,0)"]
B --> B1["False"]
C --> D["match(1,2)"]
C --> E["match(2,0)"]
D --> D1["False"]
E --> F["match(2,2)"]
F --> F1["True"]
Each * node splits into a zero-copies branch (j+2) and a one-more-copy branch (i+1).
Approach 2 — Top-down memoization
Whether s[i:] matches p[j:] depends only on (i, j). There are (len(s)+1)·(len(p)+1) such pairs, so caching each result turns the exponential recursion into work proportional to the number of states.
State / recurrence. match(i, j) = does the suffix s[i:] match the suffix p[j:]. Let first = s[i] is present and equals p[j] (or p[j] == '.'). If p[j+1] == '*': match(i, j) = match(i, j+2) or (first and match(i+1, j)). Otherwise match(i, j) = first and match(i+1, j+1). Base: match(len(s), len(p)) = True.
from functools import lru_cache
def isMatch(s: str, p: str) -> bool:
@lru_cache(maxsize=None)
def match(i: int, j: int) -> bool:
if j == len(p):
return i == len(s)
first = i < len(s) and (p[j] == '.' or p[j] == s[i])
if j + 1 < len(p) and p[j + 1] == '*':
return match(i, j + 2) or (first and match(i + 1, j))
return first and match(i + 1, j + 1)
return match(0, 0)
Complexity: O(len(s)·len(p)) time and space.
Approach 3 — Bottom-up tabulation (the 2-D table)
State / recurrence. dp[i][j] = does the prefix s[:i] match the prefix p[:j]. Write hit(i, j) for “p[j-1] matches s[i-1]”, i.e. p[j-1] == '.' or p[j-1] == s[i-1].
dp[0][0] = True
dp[0][j] = dp[0][j-2] if p[j-1] == '*' (char* matches empty)
For i >= 1:
if p[j-1] == '*':
dp[i][j] = dp[i][j-2] # zero copies of p[j-2]
or (hit(i, j-1) and dp[i-1][j]) # one more copy, if p[j-2] matches s[i-1]
else:
dp[i][j] = hit(i, j) and dp[i-1][j-1]
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 2]
if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
dp[i][j] = dp[i][j] or dp[i - 1][j]
else:
if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
Walkthrough with s = "aa", p = "a*" (m=2, n=2). First row: dp[0][0] = True; p[1] == '*' so dp[0][2] = dp[0][0] = True (a* matches empty). Row i=1: at j=2 (*), dp[1][2] = dp[1][0] (False) or (p[0]=='a'==s[0] and dp[0][2]=True) → True. Row i=2: at j=2, dp[2][2] = dp[2][0] (False) or ('a'==s[1] and dp[1][2]=True) → True. So dp[2][2] = True.
Complexity: O(m·n) time, O(m·n) space.
Approach 4 — Space-optimized (two rolling rows)
The * case reads dp[i-1][j] (row above) and dp[i][j-2] (same row, earlier). Only the previous row is needed, so keep prev and build curr.
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
prev = [False] * (n + 1)
prev[0] = True
for j in range(1, n + 1):
if p[j - 1] == '*':
prev[j] = prev[j - 2]
for i in range(1, m + 1):
curr = [False] * (n + 1)
for j in range(1, n + 1):
if p[j - 1] == '*':
curr[j] = curr[j - 2]
if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
curr[j] = curr[j] or prev[j]
else:
if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
curr[j] = prev[j - 1]
prev = curr
return prev[n]
Complexity: O(m·n) time, O(n) space.
Common pitfalls
- Treating
* as “any sequence” (that is glob/.*), instead of “zero or more of the single preceding element”. a* is only a’s.
- Forgetting the empty-string first row: a pattern like
"a*b*" must match "", which needs dp[0][j] = dp[0][j-2] seeding.
- In the
* branch, checking the wrong preceding character — the repeated element is p[j-2], not p[j-1].
- Matching a prefix rather than the whole string; the answer is
dp[m][n], requiring both to be fully consumed.
Pattern takeaway
Prefix-vs-prefix matching between two sequences is a 2-D DP indexed by how much of each you have consumed. Operators that consume a variable amount (like *) become an OR over their possible expansions: here “zero copies” (dp[i][j-2]) OR “one more copy” (dp[i-1][j]). Isolate a small matches(char, patternChar) predicate, enumerate the pattern’s cases, then collapse to rolling rows since only the previous row is read.