Regular Expression Matching
Hard · Backtracking · String · Dynamic Programming · Recursion
Problem
Given a string s and a pattern p, decide whether the pattern matches the whole of s (not just part of it). The pattern supports two special characters:
- . matches any single character;
- * matches zero or more repetitions of the character (or .) immediately before it.
Return True if p matches all of s, and False otherwise.
Examples
Input: s = "abbbc", p = "ab*c" Output: true
b* absorbs the three b’s, and a and c match themselves.
Input: s = "ac", p = "a.c" Output: false
The dot must consume exactly one character, so the pattern needs three characters.
Input: s = "xyz", p = ".*z" Output: true
.* covers xy and the final z matches literally.
Constraints
- 1 <= len(s) <= 20
- 1 <= len(p) <= 20
- s contains only lowercase English letters
- p contains only lowercase English letters, "." and "*"
- Every "*" in p follows a letter or a "."
Approaches
- Plain recursion (backtracking) — time exponential in the number of stars, space O(m + n) recursion depth
Follow-up
Real regex engines compile the pattern into an automaton: Thompson’s construction gives an NFA that is simulated in O(m · n) without backtracking. Engines that backtrack instead can take exponential time on patterns like (a*)*b, which is the cause of “ReDoS” attacks.
Related problems
Start free on Cariara · Coding problems · System design studio
