Regular Expression Matching
Match a string against a pattern with '.' and '*' using a 2D DP table: a star pair matches zero copies or eats one more letter.
Problem Understanding
Regular Expression Matching: implement matching of a string s against a pattern p where . matches any single letter and * matches zero or more of the element right before it. The match must cover the whole string.
Examples: s = "aa", p = "a" is false; p = "a*" is true; s = "ab", p = ".*" is true.
The Intuition: Treat 'x*' as One Unit
Read the pattern in units: a single letter, a ., or a pair x*. Now ask whether the first i letters of s match the first j characters of p:
- A letter or
.must matchs[i - 1], and the rest must already match:dp[i - 1][j - 1]. - A pair
x*used zero times disappears:dp[i][j - 2]. - A pair
x*used once more eatss[i - 1]ifxmatches it, and the same pair stays available:dp[i - 1][j].
The third case is the key: staying in column j lets one pair absorb any number of letters, one row at a time. Without a table, trying every count for every star repeats the same subproblems again and again; the (m + 1) × (n + 1) grid computes each one once. It is the same two-string table as Edit Distance and Interleaving String, a core dynamic programming pattern.
Interactive Walkthrough
The pattern runs across the top and the string down the left. Each cell shows T or F, and the cell its true came from is tinted. Try Trailing c to watch .* fill a whole column with T while the final c stays F.
Dry Run Table
Input: s = "aab" (down), p = "c*a*b" (across)
| ∅ | 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 |
- Row ∅:
c*andc*a*match the empty string (zero copies), so those columns are T. - Row 2, column
a*:a*eats the seconda, reading the T above it. - Row 3, column
b:bmatches and the diagonaldp[2][4]is T.
Answer: true.
The Solution Template
A bottom-up table that runs row 0 too, so star pairs can match the empty string. LeetCode guarantees every * follows a valid character, so j - 2 is never negative there.
Regular Expression Matching Code
1var isMatch = function(s, p) {2 const m = s.length, n = p.length;3 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));4 dp[0][0] = true;5 const matches = (i, j) => p[j] === '.' || p[j] === s[i];6 for (let i = 0; i <= m; i++) {7 for (let j = 1; j <= n; j++) {8 if (p[j - 1] === '*') {9 dp[i][j] = dp[i][j - 2]10 || (i > 0 && matches(i - 1, j - 2) && dp[i - 1][j]);11 } else {12 dp[i][j] = i > 0 && matches(i - 1, j - 1) && dp[i - 1][j - 1];13 }14 }15 }16 return dp[m][n];17};
Edge Cases & Common Mistakes
- Skipping row 0: patterns like
"a*b*"match the empty string; without row 0,s = "b",p = "a*b"returns false. - Treating
*as a wildcard on its own: it always modifies the character before it;"a*"can be empty,"a"cannot. A standalone*is Wildcard Matching. - Partial matches: the whole string must match, so
"a"does not match"aa". .*is not "anything at the end":".*c"still needs a finalc.- Recursion without memo: each star branches on zero or one more copy; without caching
(i, j)the work grows exponentially. Memoised top-down recursion gives the same O(m · n) as the table.
Summary
Set dp[0][0] = true and fill every row, including the empty string. A letter or . reads the diagonal; x* reads two to the left (zero copies) or straight up when x matches (one more copy). Return dp[m][n]. O(m · n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet