← DSA Atlas
Dedicated problem page · #10

Regular Expression Matching

HardTwo-Dimensional Dynamic ProgrammingPattern-matching grid DP with star lookback2D dynamic programming
Solve on LeetCode ↗
10
HardTwo-Dimensional Dynamic Programming2D dynamic programmingPattern-matching grid DP with star lookback

Regular Expression Matching

Given an input string s and a pattern p, return true if p matches the entire string s. The pattern supports '.', which matches any single character, and '*', which matches zero or more of the character immediately preceding it. The match must cover the whole string, not a partial prefix.

Open official problem prompt ↗
In plain English

We want to know whether the pattern, with '.' and '*', can be stretched to cover the whole input string exactly.

Picture it like this

Like checking a filename against a shell-style rule where 'a*' can expand to any number of a's, and testing every legal expansion at once.

Example
Input
s = "aa", p = "a*"
Output
true
Why
'a*' means zero or more 'a', which can match the two a's in "aa".
Constraints
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English lettersp contains lowercase letters, '.', and '*'Each '*' is preceded by a valid character or '.'
Pattern lesson

See the pattern, then code

Pattern-matching grid DP with star lookback
Recognition clue

A pattern with '*' meaning 'zero or more of the previous element' forces a lookback of two, which points to a 2D DP over s and p rather than a greedy scan.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. A '*' has two independent choices: use zero copies of the preceding element (skip 'x*' entirely) or, if that element matches the current character, consume one character and stay on the same star.

New words, made simpleKnow these before the algorithm
'.' wildcard
Matches exactly one arbitrary character.
'*' quantifier
Matches zero or more copies of the single element right before it.
Full match
The pattern must consume all of s, not just a prefix.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Backtracking recursion

Correct but blows up on patterns full of stars with matching characters.

Recurse, and on '*' try skipping it or consuming one character then recursing again.

Time Exponential in the worst caseSpace O(m+n) recursion depth
Best choice2D bottom-up DP

Memoizes every prefix pair once; the reliable optimal approach.

Table dp[i][j] over prefixes of s and p, handling '*' with a two-cell lookback.

Time O(m*n)Space O(m*n)
The rule we keep true

Invariant

dp[i][j] is true exactly when pattern prefix p[:j] matches string prefix s[:i].

Why this is correct

Reasoning

For a non-star token the match reduces cleanly to the diagonal. For 'x*' every possibility is captured by two disjoint cases: zero occurrences (ignore the pair, dp[i][j-2]) or at least one occurrence when x matches s[i-1] (consume that character, dp[i-1][j]). Their OR is exhaustive, so induction over prefixes gives correctness.

The algorithm in three movesSay these aloud before coding
1Define dp[i][j] = does p[:j] match s[:i]

dp[0][2] = True (a* -> empty)

2Seed empty-string patterns like a*b* via dp[0][j] = dp[0][j-2] on '*'

dp[1][2] = True (matches 'a')

3On '*': set dp[i][j] = dp[i][j-2] (zero use); if p[j-2] matches s[i-1], OR in dp[i-1][j] (one more use)

dp[2][2] = True (matches 'aa')

4On a literal or '.': dp[i][j] = dp[i-1][j-1] when the characters match

5Return dp[m][n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
a0
*1
1 · Reads='', p='a*'
2 · AskCan a* match empty?
3 · Update statedp[0][2] = dp[0][0] = True
4 · ResultTrue (zero a's)
Key takeaway

The pattern a* consumes zero, then one, then two a's as the star repeats.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-7Empty-string patterns

    Patterns like a*b*c* can match an empty s; dp[0][j]=dp[0][j-2] propagates that.

  2. 2
    Lines 11-14Star handling

    Start with zero use (dp[i][j-2]); if the preceding element matches the current char, also allow one more use via dp[i-1][j].

  3. 3
    Lines 15-16Literal or dot

    A single matching token carries the diagonal forward.

  4. 4
    Lines 17Return

    dp[m][n] answers the full match.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Pattern '.*' matches any string including empty
  • Leading '*' is invalid per constraints and never occurs
  • Empty s with pattern of only 'x*' pairs matches
!

Common beginner mistakes

  • Treating '*' as 'match anything' like glob rather than 'zero or more of the previous char'
  • Indexing p[j-2] out of bounds by not seeding dp[0][j] correctly
  • Only checking prefix match instead of the full string
Check your understanding

For 'x*', why is the 'one more use' branch dp[i-1][j] and not dp[i-1][j-2]?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles#64Minimum Path SumGrid path DP (right/down accumulation)