Regular Expression Matching

The key idea

Let dp[i][j] mean the first i chars of s match the first j chars of p. A '*' is the only tricky token: it can erase its preceding char (use dp[i][j-2]) or consume one more matching s char (use dp[i-1][j]). Everything else is a single-character match that depends on the diagonal dp[i-1][j-1].

Problem

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 s — not a partial match. Return true if p matches the whole of s, and false otherwise.

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 that for each appearance of *, there will be a previous valid character to match

Examples

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

Input: s = "aa", p = "a*" Output: true

Input: s = "ab", p = ".*" Output: true

Complexity

Time: O(m * n) Space: O(m * n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →