Regular Expression Matching (LeetCode 10)
You're given a text string s and a regex-style pattern p built from ordinary characters plus two special ones: '.', which stands for any single character, and '*', which repeats the element right before it zero or more times.
Determine whether p matches s in full, start to end -- a partial match doesn't count.
Worked Examples
s = "aa", p = "a"falses = "aa", p = "a*"trues = "ab", p = ".*"true⚖️Formal Constraints & Bounds
1 <= s.length <= 201 <= p.length <= 20scontains only lowercase English letters.pcontains only lowercase English letters,'.', and'*'.It is guaranteed for each appearance of the character
'*', there will be a previous valid character to match.
Core Insight
Regex's '' always modifies the SINGLE element immediately before it (never the raw '' symbol alone), so its transition must look 2 positions back in the pattern to skip the whole 'element*' pair (dp[i][j-2]) or 1 position back in the string to repeat that same element (dp[i-1][j]).
Real-World Scenario & Production Applications
Regex engines behind log-parsing, input validation, and search tools; compiler lexer token matching.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as True iff s[:i] fully matches p[:j]. Because '*' always modifies the single element immediately before it, the base row must skip by 2 when it sees '*': an all-'element*' pattern like "a*b*c*" can still match the empty string.
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] # skip the whole element* pairStep-by-Step Execution Trace Table
| s prefix | p prefix | Rule Applied | dp Cell Value |
|---|---|---|---|
| "" | "" | Base case | True |
| "" | "a*" | '*' zeroes out preceding 'a' (dp[0][j-2]) | True |
| "a" | "a*" | '*' repeats 'a' once (dp[i-1][j]) | True |
| "aa" | "a*" | Final cell: full match | True |
| 1 | dp = [[False]*(n+1) for _ in range(m+1)] |
| 2 | dp[0][0] = True |
| 3 | for j in range(1, n + 1): |
| 4 | if p[j-1] == '*': |
| 5 | dp[0][j] = dp[0][j-2] |
| 6 | for i in range(1, m + 1): |
| 7 | for j in range(1, n + 1): |
| 8 | if p[j-1] in ('.', s[i-1]): |
| 9 | dp[i][j] = dp[i-1][j-1] |
| 10 | elif p[j-1] == '*': |
| 11 | dp[i][j] = dp[i][j-2] |
| 12 | if p[j-2] in ('.', s[i-1]): |
| 13 | dp[i][j] = dp[i][j] or dp[i-1][j] |
| 14 | else: |
| 15 | dp[i][j] = False |
| 16 | return dp[m][n] |
Conceptual Narrative
The hardest problem in Dual Sequence & String DP: Regular Expression Matching's '' operator (zero-or-more of the PRECEDING element, not the raw literal '') makes this one of the hardest "easy-sounding" DP problems in the entire canon.
🧭 Conceptual Foundation & Pattern Intuition
The critical trap that separates this from Wildcard Matching: in regex, '*' never appears alone -- it always modifies the single character immediately before it. So 'a*' means "zero or more 'a' characters," and '.*' means "zero or more of ANY character." This means every time the DP loop sees p[j-1] == '*', it must look back one MORE position to p[j-2] to find out what element is being repeated. Getting this indexing wrong is the single most common bug in every "hard" regex DP write-up.
👑 The Analogy: A Rubber-Stamp Duplicator, Not a Blank Wildcard
Wildcard's '*' is a rubber band that can stretch over ANY characters. Regex's '*' is a rubber-stamp duplicator bolted to exactly one preceding character (or the '.' wildcard character) -- it can only print that SAME element zero, one, or many times in a row. So dp[i][j] for a '*' cell must consider two completely different hypotheses: (1) the 'element*' pair contributed nothing to the match (treat it as if it weren't there at all: dp[i][j-2]), or (2) the element the '*' is stamping actually matches the current source character s[i-1], so one more copy can be "peeled off" while keeping the SAME 'element*' pair available for peeling again (dp[i-1][j]).
🔑 The Key Idea in the Code
Notice dp[i][j] = dp[i][j-2] looks BACKWARD in the pattern by 2 (skipping the whole element* pair), while the repeat case dp[i-1][j] looks backward in the STRING by 1 but stays at the SAME pattern column j -- because the same '*' might need to consume several more source characters in a row.
Independent asterisk evaluation: Treating
*as an independent token. In regex,*always modifies the preceding character. You must inspectp[j-1] == '*'and evaluate the preceding characterp[j-2].Zero-occurrence branch omission: Forgetting the zero-occurrence transition for
x*.dp[i][j]must always inheritdp[i][j-2](completely discarding the character and asterisk pair).Preceding dot match condition: When evaluating the 1-or-more match branch for
.*, forgetting to verify that eitherp[j-2] == s[i-1]ORp[j-2] == '.'before allowingdp[i][j] = dp[i-1][j].
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Boolean full-string match against a pattern where '*' modifies the single preceding element (not itself a raw wildcard), plus '.' for any single character.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] is True iff s[:i] can be fully matched by p[:j], where '*' is always paired with the character immediately before it in p.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Treating '*' like Wildcard Matching's free-standing wildcard instead of a suffix on the preceding element -- must look back to p[j-2], not just p[j-1].
Forgetting the base row must skip by 2 (
dp[0][j] = dp[0][j-2]) to respect theelement*pairing, not skip by 1 like Wildcard Matching's base row.Missing the OR:
dp[i][j] = dp[i][j-2](zero occurrences) must be combined withdp[i-1][j](one more occurrence) only whenp[j-2]actually matchess[i-1].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build an
(m+1) x (n+1)boolean grid withdp[0][0] = True. The base row only advances by 2:dp[0][j] = dp[0][j-2]whenp[j-1] == '*'. For each cell, '.' or a literal match inheritsdp[i-1][j-1]. For '*', I first assume zero occurrences of the paired element:dp[i][j] = dp[i][j-2]; then, if that element (p[j-2]) matchess[i-1]or is '.', I OR indp[i-1][j]to allow one more repetition. Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D boolean DP table for string s of length M and pattern p of length N. Each cell does O(1) work: diagonal inheritance for '.'/literal, or a 2-way OR that looks back 2 pattern columns for '*'.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Full (M+1) x (N+1) boolean grid retained (can be rolled to O(N) with two 1D rows).
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = dp[i-1][j-1]
O(1) diagonal inheritance when characters match or pattern char is '.'.
dp[i][j] = dp[i][j-2] or (match(p[j-2], s[i-1]) and dp[i-1][j])
O(1) OR of 'skip the whole element* pair' and 'repeat the paired element one more time'.
O(M · N) total cells
Every cell computed exactly once in row-major order.
Variable Definitions
Length of the input string s
Length of the pattern p
Memory Architecture & Bounds
O(1) Iterative
O(M · N) boolean grid (or O(N) with rolling rows)
O(1) boolean result
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "'.' matches any char", "'*' matches zero or more of preceding element". Lookback token alignment: unlike LC 44, the star in regex binds strictly to the PRECEDING token .
. Small dimensions allow full 2D table or memoized recursion.
Regular Expression Matching (LeetCode 10)
You're given a text string s and a regex-style pattern p built from ordinary characters plus two special ones: '.', which stands for any single character, and '*', which repeats the element right before it zero or more times.
Determine whether p matches s in full, start to end -- a partial match doesn't count.
Worked Examples
s = "aa", p = "a"falses = "aa", p = "a*"trues = "ab", p = ".*"true⚖️Formal Constraints & Bounds
1 <= s.length <= 201 <= p.length <= 20scontains only lowercase English letters.pcontains only lowercase English letters,'.', and'*'.It is guaranteed for each appearance of the character
'*', there will be a previous valid character to match.
Core Insight
Regex's '' always modifies the SINGLE element immediately before it (never the raw '' symbol alone), so its transition must look 2 positions back in the pattern to skip the whole 'element*' pair (dp[i][j-2]) or 1 position back in the string to repeat that same element (dp[i-1][j]).
Real-World Scenario & Production Applications
Regex engines behind log-parsing, input validation, and search tools; compiler lexer token matching.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as True iff s[:i] fully matches p[:j]. Because '*' always modifies the single element immediately before it, the base row must skip by 2 when it sees '*': an all-'element*' pattern like "a*b*c*" can still match the empty string.
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] # skip the whole element* pairStep-by-Step Execution Trace Table
| s prefix | p prefix | Rule Applied | dp Cell Value |
|---|---|---|---|
| "" | "" | Base case | True |
| "" | "a*" | '*' zeroes out preceding 'a' (dp[0][j-2]) | True |
| "a" | "a*" | '*' repeats 'a' once (dp[i-1][j]) | True |
| "aa" | "a*" | Final cell: full match | True |
| 1 | dp = [[False]*(n+1) for _ in range(m+1)] |
| 2 | dp[0][0] = True |
| 3 | for j in range(1, n + 1): |
| 4 | if p[j-1] == '*': |
| 5 | dp[0][j] = dp[0][j-2] |
| 6 | for i in range(1, m + 1): |
| 7 | for j in range(1, n + 1): |
| 8 | if p[j-1] in ('.', s[i-1]): |
| 9 | dp[i][j] = dp[i-1][j-1] |
| 10 | elif p[j-1] == '*': |
| 11 | dp[i][j] = dp[i][j-2] |
| 12 | if p[j-2] in ('.', s[i-1]): |
| 13 | dp[i][j] = dp[i][j] or dp[i-1][j] |
| 14 | else: |
| 15 | dp[i][j] = False |
| 16 | return dp[m][n] |
Conceptual Narrative
The hardest problem in Dual Sequence & String DP: Regular Expression Matching's '' operator (zero-or-more of the PRECEDING element, not the raw literal '') makes this one of the hardest "easy-sounding" DP problems in the entire canon.
🧭 Conceptual Foundation & Pattern Intuition
The critical trap that separates this from Wildcard Matching: in regex, '*' never appears alone -- it always modifies the single character immediately before it. So 'a*' means "zero or more 'a' characters," and '.*' means "zero or more of ANY character." This means every time the DP loop sees p[j-1] == '*', it must look back one MORE position to p[j-2] to find out what element is being repeated. Getting this indexing wrong is the single most common bug in every "hard" regex DP write-up.
👑 The Analogy: A Rubber-Stamp Duplicator, Not a Blank Wildcard
Wildcard's '*' is a rubber band that can stretch over ANY characters. Regex's '*' is a rubber-stamp duplicator bolted to exactly one preceding character (or the '.' wildcard character) -- it can only print that SAME element zero, one, or many times in a row. So dp[i][j] for a '*' cell must consider two completely different hypotheses: (1) the 'element*' pair contributed nothing to the match (treat it as if it weren't there at all: dp[i][j-2]), or (2) the element the '*' is stamping actually matches the current source character s[i-1], so one more copy can be "peeled off" while keeping the SAME 'element*' pair available for peeling again (dp[i-1][j]).
🔑 The Key Idea in the Code
Notice dp[i][j] = dp[i][j-2] looks BACKWARD in the pattern by 2 (skipping the whole element* pair), while the repeat case dp[i-1][j] looks backward in the STRING by 1 but stays at the SAME pattern column j -- because the same '*' might need to consume several more source characters in a row.
Independent asterisk evaluation: Treating
*as an independent token. In regex,*always modifies the preceding character. You must inspectp[j-1] == '*'and evaluate the preceding characterp[j-2].Zero-occurrence branch omission: Forgetting the zero-occurrence transition for
x*.dp[i][j]must always inheritdp[i][j-2](completely discarding the character and asterisk pair).Preceding dot match condition: When evaluating the 1-or-more match branch for
.*, forgetting to verify that eitherp[j-2] == s[i-1]ORp[j-2] == '.'before allowingdp[i][j] = dp[i-1][j].
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Boolean full-string match against a pattern where '*' modifies the single preceding element (not itself a raw wildcard), plus '.' for any single character.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] is True iff s[:i] can be fully matched by p[:j], where '*' is always paired with the character immediately before it in p.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Treating '*' like Wildcard Matching's free-standing wildcard instead of a suffix on the preceding element -- must look back to p[j-2], not just p[j-1].
Forgetting the base row must skip by 2 (
dp[0][j] = dp[0][j-2]) to respect theelement*pairing, not skip by 1 like Wildcard Matching's base row.Missing the OR:
dp[i][j] = dp[i][j-2](zero occurrences) must be combined withdp[i-1][j](one more occurrence) only whenp[j-2]actually matchess[i-1].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build an
(m+1) x (n+1)boolean grid withdp[0][0] = True. The base row only advances by 2:dp[0][j] = dp[0][j-2]whenp[j-1] == '*'. For each cell, '.' or a literal match inheritsdp[i-1][j-1]. For '*', I first assume zero occurrences of the paired element:dp[i][j] = dp[i][j-2]; then, if that element (p[j-2]) matchess[i-1]or is '.', I OR indp[i-1][j]to allow one more repetition. Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D boolean DP table for string s of length M and pattern p of length N. Each cell does O(1) work: diagonal inheritance for '.'/literal, or a 2-way OR that looks back 2 pattern columns for '*'.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Full (M+1) x (N+1) boolean grid retained (can be rolled to O(N) with two 1D rows).
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = dp[i-1][j-1]
O(1) diagonal inheritance when characters match or pattern char is '.'.
dp[i][j] = dp[i][j-2] or (match(p[j-2], s[i-1]) and dp[i-1][j])
O(1) OR of 'skip the whole element* pair' and 'repeat the paired element one more time'.
O(M · N) total cells
Every cell computed exactly once in row-major order.
Variable Definitions
Length of the input string s
Length of the pattern p
Memory Architecture & Bounds
O(1) Iterative
O(M · N) boolean grid (or O(N) with rolling rows)
O(1) boolean result
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "'.' matches any char", "'*' matches zero or more of preceding element". Lookback token alignment: unlike LC 44, the star in regex binds strictly to the PRECEDING token .
. Small dimensions allow full 2D table or memoized recursion.