LeetCode · #10

Regular Expression Matching Solution

Implement regular expression matching with . (any char) and * (zero or more of preceding element).

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #10

🏗️

Pattern

DP — 2D regex matching

Given string s and pattern p, implement regex matching where . matches any single character and * matches zero or more of the preceding element. The match must cover the entire string.

Example

Input: s = "aab", p = "c*a*b" Output: true // c* = "" (zero c's), a* = "aa", b = "b" → "aab" ✓

Constraints

• 1 ≤ s.length ≤ 20 • 1 ≤ p.length ≤ 20  ← small enough for any correct approach • p contains only lowercase letters, '.', and '*' • '*' is always preceded by a valid character or '.'

Section Two · Approach 1

Recursion — exponential

Process pattern left to right. If the next pattern character has a *, try matching zero occurrences (skip the pair) or one occurrence (if char matches, advance in string but keep pattern). Otherwise, match one character and advance both.

Why it works

Exhaustively tries all ways to apply * (zero or more matches) and direct matches. If any branch succeeds, the match is valid.

Why we can do better

Problem: Without memoization, the branching on * causes exponential blowup. States are (i,j) — position in s and p. At most m×n unique states. 2D DP stores each once.

Java — Recursive

 class Solution {
public boolean isMatch(String s, String p) {
if (p.isEmpty()) return s.isEmpty();
boolean firstMatch = !s.isEmpty() &&
            (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.');
if (p.length() >= 2 && p.charAt(1) == '*')
return isMatch(s, p.substring(2)) // zero occurrences
|| (firstMatch && isMatch(s.substring(1), p)); // one+ occurrence return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

Python — Recursive

 class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p: return not s
        first = bool(s) and p[0] in (s[0], '.')
if len(p) >= 2 and p[1] == '*':
return self.isMatch(s, p[2:]) or (first and self.isMatch(s[1:], p))
return first and self.isMatch(s[1:], p[1:])

Metric	Value
Time	Exponential without memo
Space	O(m+n)

Section Three · Approach 2

2D DP — O(m·n)

dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Handle three cases: direct character match, . wildcard, and * repetition.

💡 Mental model: Imagine a lock with a combination dial (the pattern) and a key (the string). . is a universal pin that matches any notch. * is a spring-loaded section that can stretch to match zero or more notches of the preceding pin type. The grid maps every (key position, dial position) pair: "Can the remaining key match the remaining dial?" You fill this grid bottom-right to top-left (or top-left to bottom-right with careful indexing).

Algorithm

dp[0][0] = true (empty string matches empty pattern).
First row: dp[0][j] = true if p[j-1]=='*' and dp[0][j-2] is true (a* matches "").
For i=1..m, j=1..n:
If p[j-1] is letter or .: dp[i][j] = dp[i-1][j-1] if chars match.
If p[j-1]=='*': dp[i][j] = dp[i][j-2] (zero occurrences) OR (dp[i-1][j] if s[i-1] matches p[j-2] — one more occurrence).
Return dp[m][n].

🎯 When to recognize this pattern: "Pattern matching with wildcards (*,?)." The signal: two-string matching where one has special characters. * handling is the tricky part — it's always a "zero or more" choice. Related: LC 44 (Wildcard Matching — * matches any sequence, slightly different semantics).

Key insight for *: p[j-1]=='*' has two sub-cases: (1) Use zero of the preceding char → dp[i][j-2]. (2) Use one more of the preceding char → dp[i-1][j] if current string char matches the preceding pattern char. Case (2) is recursive — if we match one more, we stay at j (the * still applies), but advance i.

Section Four · Trace

Visual Walkthrough

Trace for s="aab", p="c*a*b".

Regex Matching — 2D DP (s="aab", p="c*a*b")

Section Five · Implementation

Code — Java & Python

Java — 2D DP

 class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
// Handle patterns like a*, a*b*, a*b*c* matching empty string for (int j = 2; j <= n; j++)
if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char sc = s.charAt(i-1), pc = p.charAt(j-1);
if (pc == '.' || pc == sc)
                    dp[i][j] = dp[i-1][j-1]; // direct match else if (pc == '*') {
                    dp[i][j] = dp[i][j-2]; // zero occurrences char prev = p.charAt(j-2);
if (prev == '.' || prev == sc)
                        dp[i][j] |= dp[i-1][j]; // one more occurrence
}
            }
return dp[m][n];
    }
}

Python — 2D DP

 class Solution:
def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True for j in range(2, n+1):
if p[j-1] == '*': dp[0][j] = dp[0][j-2]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] in (s[i-1], '.'):
                    dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
                    dp[i][j] = dp[i][j-2] # zero if p[j-2] in (s[i-1], '.'):
                        dp[i][j] |= dp[i-1][j] # one+ return dp[m][n]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion (no memo)	Exponential	O(m+n)	Simple but slow
Memoized recursion	O(m·n)	O(m·n)	Top-down; cleaner logic
2D DP ← optimal	O(m·n)	O(m·n)	Bottom-up; handles all edge cases cleanly

LC 10 vs LC 44 (Wildcard Matching): In LC 10, * means zero or more of the preceding element (regex semantics). In LC 44, * matches any sequence of characters (glob semantics). The DP transitions differ: LC 10's * references p[j-2], while LC 44's * is standalone. Don't mix them up.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty pattern	`s="a", p=""`	p is empty but s isn't. dp[1][0]=false.
Star matches zero	`s="a", p="ab*"`	b* = "". Pattern becomes "a". Match.
Dot-star	`s="anything", p=".*"`	.* matches any string of any length.
Multiple stars	`s="aab", p="cab"`	c="" then a="aa" then b="b".
Star at start	Not possible	Constraints guarantee * is always preceded by valid char.

⚠ Common Mistake: For the * case, checking dp[i-1][j-1] instead of dp[i-1][j] for "one more occurrence." When * matches one more character, the * is still active — we stay at column j (not j-1). dp[i-1][j] means "same pattern (including the *), one fewer string char" — allowing another match next iteration.

← Back to DP — 2D problems

LearningTree

LC 10 · Regular Expression Matching — Solution & Explanation | DSA Guide