Regular Expression Matching

Explanation & Solution

Description

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

The matching should cover the entire input string (not partial).

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Constraints

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters
p contains only lowercase English letters, '.', and '*'
It is guaranteed for each appearance of '*', there will be a previous valid character to match

Approach

Dynamic Programming pattern

1. Define the DP Table

Create a 2D boolean array dp of size (m+1) x (n+1)
dp[i][j] represents whether s[0..i-1] matches p[0..j-1]
Set dp[0][0] = true (empty string matches empty pattern)

2. Handle Empty String Base Cases

Patterns like a*, a*b*, a*b*c* can match an empty string
For j from 2 to n: if p[j-1] === '*', then dp[0][j] = dp[0][j-2] (skip the x* pair)

3. Process the `'*'` Wildcard

When p[j-1] === '*', two choices:
Zero occurrences: ignore the x* pair entirely, so dp[i][j] = dp[i][j-2]
One or more occurrences: if the preceding character p[j-2] matches s[i-1] (or is '.'), then dp[i][j] = dp[i-1][j] (consume one character from s, keep the * active)

4. Process Literal and `'.'` Characters

If p[j-1] is '.' or matches s[i-1] exactly, then dp[i][j] = dp[i-1][j-1]
Otherwise dp[i][j] remains false

5. Return the Result

dp[m][n] tells us whether the entire string s matches the entire pattern p

Key Insight

The '*' operator is the tricky part: it can consume zero or more characters, requiring two separate transitions in the DP
The dp[i-1][j] transition for * is powerful: it says "match one more character and keep the star active", which naturally handles multiple repetitions

Time

O(m * n) where m and n are the lengths of s and p

Space

O(m * n) for the DP table

Visualization

Input:

[a, a], p = a

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Edit Distance

Burst Balloons