A complete visual walkthrough of the dynamic programming approach — from recursion to the 2D table.
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.'*' Matches zero or more of the preceding element.Return a boolean indicating whether the matching covers the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English letters.p contains only lowercase English letters, '.', and '*'.'*', there will be a previous valid character to match.Given a string s and a pattern p, implement regular expression matching with two special characters:
The matching must cover the entire input string, not just a substring.
The natural approach is recursion: compare characters from the start, and when we encounter *, branch into two choices — use it or skip it.
For s="aab", p="c*a*b", the recursion branches at every *:
Many subproblems are solved repeatedly. With longer inputs, the tree grows exponentially — O(2^(m+n)) in the worst case.
Overlapping subproblems! The recursive solution re-computes the same (i, j) pairs many times. This is the classic signal that dynamic programming will help — we can memoize results in a 2D table and solve each subproblem exactly once.
Define dp[i][j] = "does s[0..i-1] match p[0..j-1]?" We build a 2D boolean table bottom-up, where each cell depends on previously computed cells.
Each cell dp[i][j] can depend on up to three other cells, depending on the pattern character:
Let's trace through s = "aab", p = "c*a*b" step by step. We fill the table row by row, left to right.
dp[0][0] = true — empty string matches empty pattern. Then for row 0 (empty string), we check if patterns like c*, c*a*, etc. can match the empty string by using the "star zero" rule.
| "" | c | * | a | * | b | |
|---|---|---|---|---|---|---|
| "" | T | F | T | F | T | F |
| a | F | ? | ? | ? | ? | ? |
| a | F | ? | ? | ? | ? | ? |
| b | F | ? | ? | ? | ? | ? |
Row 0: dp[0][2]=T because c* can match "" (skip c*). dp[0][4]=T because c*a* can match "" (skip both). dp[0][5]=F because "b" cannot match "".
Now we process s[0] = 'a' against each pattern prefix:
| "" | c | * | a | * | b | |
|---|---|---|---|---|---|---|
| "" | T | F | T | F | T | F |
| a | F | F | F | T | T | F |
| a | F | ? | ? | ? | ? | ? |
| b | F | ? | ? | ? | ? | ? |
dp[1][3] exact p[2]='a' == s[0]='a', so dp[1][3] = dp[0][2] = T
dp[1][4] star zero skip a*: dp[1][2] = F. star 1+ p[2]='a'==s[0]='a': dp[0][4] = T. Result: T
After filling all rows, the answer is at dp[3][5] — the bottom-right cell:
| "" | 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 |
dp[3][5] = true — the string "aab" matches the pattern "c*a*b". The c* matches zero c's, a* matches two a's, and b matches b.
Why bottom-up works: Every cell only depends on cells above it, to its left, or diagonally above-left — all of which are already computed when we process row by row, left to right. No recursion needed.
s = "", p = "a*" → true. The * can match zero occurrences, effectively consuming the entire pattern. Similarly p = "a*b*c*" matches empty because every character-star pair can match zero times.
s = "a", p = "" → false. An empty pattern only matches an empty string. The DP base case handles this: dp[0][0] = true, but dp[i][0] = false for any i > 0.
s = "anything", p = ".*" → true. The . matches any single character, and * repeats it zero or more times. This is the "match everything" wildcard.
s = "aab", p = "c*a*b" → true. The c* matches zero c's, a* matches two a's, and b matches b. Each star group is processed independently in the DP table.
The pattern "*a" is invalid input per the problem constraints — * always follows a character or dot. The DP approach naturally handles this since we always look at p[j-1] when processing a * at position j.
class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); // dp[i][j] = does s[0..i-1] match p[0..j-1]? boolean[][] dp = new boolean[m + 1][n + 1]; // Base case: empty string matches empty pattern dp[0][0] = true; // Initialize row 0: patterns like a*, a*b*, a*b*c* // can match the empty string by using zero occurrences for (int j = 1; j <= n; j++) { if (p.charAt(j - 1) == '*') { dp[0][j] = dp[0][j - 2]; // skip the "x*" pair } } // Fill the table row by row for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { char sc = s.charAt(i - 1); // current string char char pc = p.charAt(j - 1); // current pattern char if (pc == '.' || pc == sc) { // Rule 1: exact match or dot wildcard // Both chars consumed → diagonal dp[i][j] = dp[i - 1][j - 1]; } else if (pc == '*') { // Rule 2: zero occurrences — skip "x*" dp[i][j] = dp[i][j - 2]; // Rule 3: one or more occurrences // Only if the char before * matches s[i-1] if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == sc) { dp[i][j] = dp[i][j] || dp[i - 1][j]; } } // else: mismatch, dp[i][j] stays false } } return dp[m][n]; // answer: does entire s match entire p? } }
func isMatch(s string, p string) bool { m, n := len(s), len(p) // dp[i][j] = does s[0..i-1] match p[0..j-1]? dp := make([][]bool, m+1) for i := range dp { dp[i] = make([]bool, n+1) } // Base case: empty string matches empty pattern dp[0][0] = true // Initialize row 0: patterns like a*, a*b*, a*b*c* // can match the empty string by using zero occurrences for j := 1; j <= n; j++ { if p[j-1] == '*' { dp[0][j] = dp[0][j-2] // skip the "x*" pair } } // Fill the table row by row for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { sc := s[i-1] // current string char pc := p[j-1] // current pattern char if pc == '.' || pc == sc { // Rule 1: exact match or dot wildcard → diagonal dp[i][j] = dp[i-1][j-1] } else if pc == '*' { // Rule 2: zero occurrences — skip "x*" dp[i][j] = dp[i][j-2] // Rule 3: one or more occurrences if p[j-2] == '.' || p[j-2] == sc { dp[i][j] = dp[i][j] || dp[i-1][j] } } // else: mismatch, dp[i][j] stays false } } return dp[m][n] // answer: does entire s match entire p? }
class Solution: def is_match(self, s: str, p: str) -> bool: m, n = len(s), len(p) # dp[i][j] = does s[0..i-1] match p[0..j-1]? dp = [[False] * (n + 1) for _ in range(m + 1)] # Base case: empty string matches empty pattern dp[0][0] = True # Initialize row 0: patterns like a*, a*b*, a*b*c* # can match the empty string by using zero occurrences for j in range(1, n + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 2] # skip the "x*" pair # Fill the table row by row for i in range(1, m + 1): for j in range(1, n + 1): sc = s[i - 1] # current string char pc = p[j - 1] # current pattern char if pc == '.' or pc == sc: # Rule 1: exact match or dot wildcard # Both chars consumed → diagonal dp[i][j] = dp[i - 1][j - 1] elif pc == '*': # Rule 2: zero occurrences — skip "x*" dp[i][j] = dp[i][j - 2] # Rule 3: one or more occurrences # Only if the char before * matches s[i-1] if p[j - 2] == '.' or p[j - 2] == sc: dp[i][j] = dp[i][j] or dp[i - 1][j] # else: mismatch, dp[i][j] stays False return dp[m][n] # answer: does entire s match entire p?
impl Solution { pub fn is_match(s: String, p: String) -> bool { let sb = s.as_bytes(); let pb = p.as_bytes(); let (m, n) = (sb.len(), pb.len()); // dp[i][j] = does s[0..i-1] match p[0..j-1]? let mut dp = vec![vec![false; n + 1]; m + 1]; // Base case: empty string matches empty pattern dp[0][0] = true; // Initialize row 0: patterns like a*, a*b*, a*b*c* // can match the empty string by using zero occurrences for j in 1..=n { if pb[j - 1] == b'*' { dp[0][j] = dp[0][j - 2]; // skip the "x*" pair } } // Fill the table row by row for i in 1..=m { for j in 1..=n { let sc = sb[i - 1]; // current string byte let pc = pb[j - 1]; // current pattern byte if pc == b'.' || pc == sc { // Rule 1: exact match or dot wildcard → diagonal dp[i][j] = dp[i - 1][j - 1]; } else if pc == b'*' { // Rule 2: zero occurrences — skip "x*" dp[i][j] = dp[i][j - 2]; // Rule 3: one or more occurrences if pb[j - 2] == b'.' || pb[j - 2] == sc { dp[i][j] = dp[i][j] || dp[i - 1][j]; } } // else: mismatch, dp[i][j] stays false } } dp[m][n] // answer: does entire s match entire p? } }
function isMatch(s: string, p: string): boolean { const m = s.length, n = p.length; // dp[i][j] = does s[0..i-1] match p[0..j-1]? const dp: boolean[][] = Array.from({length: m + 1}, () => new Array(n + 1).fill(false)); // Base case: empty string matches empty pattern dp[0][0] = true; // Initialize row 0: patterns like a*, a*b*, a*b*c* // can match the empty string by using zero occurrences for (let j = 1; j <= n; j++) { if (p[j - 1] === '*') { dp[0][j] = dp[0][j - 2]; // skip the "x*" pair } } // Fill the table row by row for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { const sc = s[i - 1]; // current string char const pc = p[j - 1]; // current pattern char if (pc === '.' || pc === sc) { // Rule 1: exact match or dot wildcard // Both chars consumed → diagonal dp[i][j] = dp[i - 1][j - 1]; } else if (pc === '*') { // Rule 2: zero occurrences — skip "x*" dp[i][j] = dp[i][j - 2]; // Rule 3: one or more occurrences // Only if the char before * matches s[i-1] if (p[j - 2] === '.' || p[j - 2] === sc) { dp[i][j] = dp[i][j] || dp[i - 1][j]; } } // else: mismatch, dp[i][j] stays false } } return dp[m][n]; // answer: does entire s match entire p? }
Enter a string and pattern, then step through the DP table cell by cell. Watch each rule in action.
We fill an (m+1) x (n+1) table, where m = |s| and n = |p|. Each cell takes O(1) work -- it checks the pattern character and looks up at most three previously computed cells (diagonal, left-by-2, or above). The table itself requires O(m × n) space.
Each * operator branches into "use it" or "skip it" at every position, creating a binary recursion tree of depth m+n. The call stack grows up to O(m+n) deep, and overlapping subproblems are recomputed exponentially.
Caches results for each (i, j) pair in a hash map, ensuring each of the m × n subproblems is solved at most once. The recursion stack still uses O(m+n) depth, and the memo table stores up to m × n entries.
Fills an (m+1) × (n+1) table iteratively, where each cell reads at most three previously computed neighbors (diagonal, left-by-2, or above) in O(1). No recursion overhead, and space can be reduced to O(n) with rolling arrays since each row only depends on the previous row.
The * operator is what makes this hard. Each * can match zero or more of the preceding element, causing exponential branching in naive recursion. The DP table collapses all that branching: each cell depends on at most 3 previous cells, and every (i, j) subproblem is solved exactly once. Space can be reduced to O(n) with rolling arrays since each row only reads from the current and previous row.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.