Appearance
4.24.11 — Regular Expression Matching
LeetCode 10 · Hard
The problem
Implement matching for two special characters:
.matches any single character.*matches zero or more of the character before it.
The match must cover the entire string, not just part of it.
s = "aa", p = "a" → false (p matches only one a)
s = "aa", p = "a*" → true (a* is two a's)
s = "ab", p = ".*" → true (.* is any sequence)
s = "aab", p = "c*a*b" → true (c* is zero c's)The pattern
Two strings, so a grid. dp[i][j] is true when the first i characters of s match the first j characters of p.
* is the only difficulty. Everything else is a character comparison.
Read the pattern in pairs: a * always attaches to the character before it, so "a*" is one unit, not two. When p[j-1] is *, the unit is p[j-2] followed by *, and it can be used two ways:
Zero occurrences. Throw the whole unit away and match s against the pattern with those two characters removed:
dp[i][j] = dp[i][j-2]
One or more occurrences. Only possible if p[j-2] matches s[i-1]. Then consume that one character of s and keep the pattern unit available for more:
dp[i][j] = dp[i-1][j]
Either works, so they are joined by or.
Note dp[i-1][j], not dp[i-1][j-2]. The j does not move, because * can match again. That single index is the difference between a* matching one a and matching many, and it is the line to get right.
When p[j-1] is not a *, it is a plain comparison:
dp[i][j] = dp[i-1][j-1] \ \text{if}\ p[j-1] = s[i-1] \ \text{or}\ p[j-1] = \text{'.'}
The base cases
dp[0][0] = True — two empty strings match.
dp[0][j] — can a non-empty pattern match the empty string? Only if it is entirely made of x* units. So for each * at position j-1, dp[0][j] = dp[0][j-2].
That is the base case people forget, and it is what makes "c*a*b" fail correctly against "" while "c*a*" succeeds.
dp[i][0] = False for i > 0 — an empty pattern matches nothing.
The solution
python
class Solution:
def isMatch(self, 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): # empty s against a pattern
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] # zero occurrences
if p[j - 2] == s[i - 1] or p[j - 2] == '.':
dp[i][j] = dp[i][j] or dp[i - 1][j] # one or more
elif p[j - 1] == s[i - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]ts
function isMatch(s: string, p: string): boolean {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}dp[i][j-2] is always the first thing tried in the * case, because zero occurrences is always allowed regardless of what s holds.
dp[i-1][j] keeps j fixed, which is what lets a* consume several characters, one per step.
p[j-2] is safe to index whenever p[j-1] is *, because a valid pattern never starts with *. The problem guarantees this; in production code you would validate it.
Trace
s = "aab", p = "c*a*b".
dp[0][2] is true because c* can be zero cs. dp[0][4] is true because a* can also be zero. Then dp[1][4] and dp[2][4] become true as a* absorbs one and then two as — each time via dp[i-1][j] with j unchanged. Finally b matches b and dp[3][5] is true ✓.
Complexity
O(mn) time and space.
The naive recursive matcher without memoisation is exponential — ".*.*.*.*b" against a long string of as is the classic timeout input, and it is the same shape as the catastrophic backtracking that causes ReDoS attacks in real regex engines. Chapter 8 covers that; mentioning it here is a good connection.
The wildcard cousin
Wildcard Matching (LeetCode 44) uses ? for any single character and * for any sequence, unattached to a preceding character. It is genuinely easier, because * stands alone:
dp[i][j] = dp[i][j-1] \ \text{(star matches empty)} \ \text{or}\ dp[i-1][j] \ \text{(star absorbs one more)}
Do not mix the two up. In this problem * modifies the previous character; in wildcard matching it does not. That difference changes the recurrence completely, and interviewers sometimes switch between them to see whether you noticed.
Where this goes next
- Wildcard Matching — above.
- A real regex engine — compiles the pattern to an NFA and simulates it, which runs in O(mn) guaranteed with no backtracking. Thompson's construction is the classic method, and it is why some engines are immune to ReDoS while backtracking engines are not.
- Interleaving String, Edit Distance — the same two-string grid.
What the interviewer will push on
"How do you handle *?" Two cases joined by or — zero occurrences via dp[i][j-2], one or more via dp[i-1][j].
"Why does j stay the same in the one-or-more case?" So * remains available to match again.
"What is dp[0][j] for?" A pattern of only x* units can match the empty string. Forgetting it breaks "c*a*b" handling.
"How is this different from wildcard *?" Here * modifies the previous character; there it stands alone.
"Why is the naive recursion exponential?" Each * branches, and the same states are recomputed. Then name ReDoS.
"How does a real regex engine avoid this?" NFA simulation, linear and backtracking-free.
One thing to volunteer: say that you read the pattern in pairs — x* is one unit — before writing anything. Almost every wrong solution to this problem treats * as an independent character.
Next: 4.25 covers the family where you do not need to consider every option at all, and the exchange argument that tells you whether greed is safe.