Regular Expression Matching: Building a Regex Engine with 2D DP
Solve LeetCode's Regular Expression Matching with a 2D dynamic programming table — the '.' and '*' rules, a worked walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Regular Expression Matching is the problem where a "just check the characters" instinct falls apart completely. The * operator doesn't mean "any character" — it means zero or more of the thing before it, and that single rule creates a branching cloud of possibilities. Does a* consume this a, or skip it entirely and let the next pattern token try? You can't know locally.
That non-local decision is exactly what dynamic programming is built for. Instead of guessing, you build a table where every cell answers one small, self-contained question, and each answer leans on answers you've already computed.
By the end you'll be able to explain why the star looks two columns back, why the diagonal carries an exact-match result forward, and why the whole thing runs in O(m·n).
The problem
Implement regex matching for an input string s and a pattern p, supporting two special characters:
.matches any single character.*matches zero or more of the character immediately before it.
The match must cover the entire string, not a substring. Return true only if all of s is consumed by all of p.
Input: s = "aab", p = "c*a*b"
Output: true
Why: c* matches zero c's, a* matches two a's, b matches b.
"" + "aa" + "b" == "aab", and the whole pattern is used.The trap in that example is c*. The pattern opens with a character that never appears in s, yet the answer is still true — because c* is allowed to match nothing at all. Any solution that treats * as "match something" gets this wrong.
The brute force baseline
The recursive version reads straight off the rules. Look at the first pattern token; if the next token is a *, branch on skip-it-entirely versus consume-one-character-and-stay.
function isMatch(s, p) {
if (p.length === 0) return s.length === 0;
const firstMatch = s.length > 0 && (p[0] === s[0] || p[0] === '.');
if (p.length >= 2 && p[1] === '*') {
// skip "x*" (zero occurrences) OR consume one char and reuse the star
return isMatch(s, p.slice(2)) || (firstMatch && isMatch(s.slice(1), p));
}
return firstMatch && isMatch(s.slice(1), p.slice(1));
}This is correct, but the two branches on every * fan out into an exponential tree. A pattern like a*a*a*a* against a long string of as re-solves the same (s, p) suffix pairs thousands of times over. Each distinct (i, j) position gets recomputed on countless paths, and nothing remembers a result once it's found. That repetition is the signal to switch to a table.
The key insight: one boolean per prefix pair
There are only m+1 possible string prefixes (including the empty one) and n+1 possible pattern prefixes. Every question the recursion asks is really "does string prefix of length i match pattern prefix of length j?" — and there are only (m+1)·(n+1) such questions.
So define:
dp[i][j] = true if s[0..i) matches p[0..j)dp[0][0] is true — an empty string matches an empty pattern. From there, each cell is decided by looking at the current characters s[i-1] and p[j-1] and reusing at most two already-filled cells. Three rules cover everything:
Current p[j-1] | Cell depends on | Reason |
|---|---|---|
a letter equal to s[i-1], or . | dp[i-1][j-1] (diagonal) | characters line up, so inherit the shorter-prefix answer |
* (zero occurrences) | dp[i][j-2] (two left) | drop the x* pair entirely |
* (one-or-more) | dp[i-1][j] (directly above) | if x matches s[i-1], consume it and keep the same * |
The * handling is the whole puzzle. It looks two columns back because x* is a two-character unit — skipping it means erasing both the letter and the star. And it looks up to model "the star soaks up one more character of s."
The optimal solution
This is the exact algorithm the visualizer animates, cell by cell.
function isMatch(s, p) {
const m = s.length;
const n = p.length;
// dp[i][j] represents if s[0..i] matches p[0..j]
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
// Empty string matched with empty pattern is true
dp[0][0] = true;
// Handle patterns with '*' matching an empty string
// e.g. s="" p="a*" -> true
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') {
// '*' eliminates previous char, so we look 2 columns back!
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] === s[i - 1] || p[j - 1] === '.') {
// Direct match or wildcard '.' match
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === '*') {
// Ignore the '*' and preceding element (0 occurrences)
dp[i][j] = dp[i][j - 2];
// Or if preceding element matches current char natively or via '.'
// (1 or more occurrences)
if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[m][n];
}Two setup details do a lot of quiet work. First, the whole grid starts false, so any cell no rule touches (a plain mismatch) is already correct without an explicit else. Second, the row-0 pre-fill handles patterns like a*b*c* matching an empty string: each * chains back two columns, so a run of erasable pairs stays true all the way across.
Walkthrough
Trace s = "aab", p = "c*a*b". The grid is 4 × 6. Rows are the empty prefix then a, a, b; columns are the empty prefix then c, *, a, *, b.
Filling row 0 first: dp[0][0] is true; c at column 1 leaves false; the * at column 2 copies dp[0][0] → true; a at column 3 stays false; the * at column 4 copies dp[0][2] → true; b at column 5 stays false.
Here is the completed table (T = true, F = false):
| i \ j | ∅ | c | * | a | * | b |
|---|---|---|---|---|---|---|
| ∅ | T | F | T | F | T | F |
| a | F | F | F | T | T | F |
| a | F | F | F | F | T | F |
| b | F | F | F | F | F | T |
The load-bearing cells:
dp[1][3](s='a'vsp='a'): letters match, so it inherits the diagonaldp[0][2] = true. This says "the pattern'sc*ate nothing, and nowamatches the firsta."dp[1][4](p='*'aftera): zero-occurrence path readsdp[1][2] = false. Buta(the char before*) equalss='a', so it also checks the cell above,dp[0][4] = true, flipping it to true. This is the star absorbing onea.dp[2][4]: same star, seconda. Zero-path isfalse, but the above-celldp[1][4] = truecarries the running match down a row — the star has now absorbed twoas.dp[3][5](s='b'vsp='b'): letters match, inherit the diagonaldp[2][4] = true.
That final true in the bottom-right corner is the answer. Notice column 1 (c) is false in every string row — c never appears in aab — yet the answer survives because c* erased itself back in row 0.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(m·n) | every cell of the (m+1)×(n+1) grid is filled once, with O(1) work each |
| Space | O(m·n) | the full 2D boolean table; reducible to O(n) with a rolling two-row buffer |
The exponential recursion collapses to a polynomial because each (i, j) prefix pair is computed exactly once and then reused, instead of being re-derived on every path that reaches it.
Common mistakes
- Treating
*as "any character." That's the glob wildcard, not regex. Here*is a quantifier on the previous token;a*means zero-or-moreas, and.*(dot then star) is what matches any string. - Forgetting the zero-occurrence branch. If you only handle "the star matches a character," you break
c*a*bonaab, becausec*must match nothing. - Skipping the row-0 pre-fill. Without it,
""never matchesa*or.*, and any pattern of erasable pairs against a short string fails. - Off-by-one on the
*lookback. The zero path isdp[i][j-2], notdp[i][j-1]— you erase two pattern characters (the letter and its star), so you land two columns left. - Reading
dp[i][j-2]before it exists. A*at pattern position 1 (no preceding character) is malformed input; LeetCode guarantees every*has a valid character before it, soj-2 >= 0always holds.
Where this pattern shows up next
The "fill a boolean grid where each cell reuses earlier cells" template powers a whole family of string and subset DP problems:
- Word Break — a 1D version of the same idea: can a prefix of the string be segmented into dictionary words?
- Longest Increasing Subsequence — DP over prefixes again, but tracking a length instead of a boolean.
- Partition Equal Subset Sum — a boolean DP grid indexed by item and target sum, structurally a cousin of this matrix.
- Coin Change II — counting DP over coins and amounts, the next step up from boolean reachability.
To watch the matrix fill in and the star's dependency arrows fire, step through Regular Expression Matching interactively.
FAQ
What is the time complexity of Regular Expression Matching with DP?
It's O(m·n) time, where m is the string length and n is the pattern length. The table has (m+1)·(n+1) cells, and each cell is decided in constant time by inspecting the current two characters and reading at most two already-filled cells. Space is O(m·n) for the full table, which you can shrink to O(n) by keeping only the previous and current rows, since no cell depends on anything more than one row up.
Why does the star operator look two columns back?
Because x* is a two-character unit in the pattern — the literal x and the * that quantifies it. Choosing "zero occurrences" means dropping that entire unit, which advances the pattern by two positions. In table terms, dp[i][j] with p[j-1] == '*' copies dp[i][j-2], skipping both the star and the character it modifies. Looking only one column back would erase the star but leave a dangling literal, which is meaningless.
How is regex * different from a wildcard *?
In filename globbing, * matches any run of characters on its own. In regular expressions, * is a quantifier that attaches to the token before it and means "zero or more of that token." So a* matches "", "a", "aa", and so on, but never "b". To match any string in regex you need .* — a dot (any single character) followed by a star (repeated zero or more times).
Can this be solved without a 2D table?
Yes, in two ways. Top-down recursion with memoization on (i, j) computes the same values lazily and is often easier to reason about. For iteration, you can compress the bottom-up table to two rows — current and previous — because every rule reads only from the same row or the row directly above, bringing space down to O(n) while keeping the O(m·n) time. The full 2D grid is the clearest to learn from, which is why the visualizer renders it in full.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.