-
Notifications
You must be signed in to change notification settings - Fork 0
151 — Regular Expression Matching
LeetCode 10 · Hard. Given an input string s and a pattern p, implement regular expression matching with support for . and * where . matches any single character and * matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Picture scanning s and p together, character by character, asking "does the rest of s from here match the rest of p from here?" Most of the time that's a simple one-character decision — does p's current character (or .) match s's current character, and if so, recurse on both moving forward one step. The wrinkle is *: seeing a * in p means the previous pattern character is optional and repeatable, which splits into two entirely different sub-questions — "skip the starred element and its * entirely" (recurse with p moved forward two, s unmoved), or "consume one more copy of it from s" (recurse with s moved forward one, p unmoved, so the same * can be reused again). Either way, the state is just "how far into s, how far into p" — two indices, one 2-D table.
"String matching with . and * wildcards" is the branching-2-D-DP tell: the state is (position in s, position in p), and most cells look at one diagonal neighbor like ordinary string-matching DP, but any cell where p's current character is * instead looks at two very different neighbors — "zero occurrences" (skip two pattern positions) and "one more occurrence" (skip one string position, stay on the same pattern position).
Recurse over (i, j) — positions in s and p — handling the * case by trying both "skip it" and "use it once more," with no memoization.
func isMatchBruteForce(_ s: String, _ p: String) -> Bool {
let sArr = Array(s), pArr = Array(p)
func match(_ i: Int, _ j: Int) -> Bool {
if j == pArr.count { return i == sArr.count }
let firstMatch = i < sArr.count && (pArr[j] == "." || pArr[j] == sArr[i])
if j + 1 < pArr.count && pArr[j + 1] == "*" {
// zero occurrences of pArr[j], or one more occurrence and retry the same pattern position
return match(i, j + 2) || (firstMatch && match(i + 1, j))
} else {
return firstMatch && match(i + 1, j + 1)
}
}
return match(0, 0)
}
// smoke test
print(isMatchBruteForce("aa", "a")) // false
print(isMatchBruteForce("aa", "a*")) // true
print(isMatchBruteForce("ab", ".*")) // true
print(isMatchBruteForce("aab", "c*a*b")) // trueBig-O: O(2^(m+n)) time in the worst case — every * offers a two-way branch, and patterns like "a*a*a*...b" against non-matching strings force exploring most combinations. O(m + n) space for the recursion stack.
Fill an (m+1) x (n+1) table where dp[i][j] is true if the first i characters of s match the first j characters of p. The pattern is guaranteed valid (a * is always preceded by a literal character or .), so whenever pArr[j-1] == "*", j >= 2 always holds.
func isMatch(_ s: String, _ p: String) -> Bool {
let sArr = Array(s), pArr = Array(p)
let m = sArr.count, n = pArr.count
var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
dp[0][0] = true
// Empty s can still match patterns like "a*" or "a*b*c*" — zero occurrences of each starred group.
if n >= 2 {
for j in 2...n where pArr[j - 1] == "*" {
dp[0][j] = dp[0][j - 2]
}
}
guard m > 0 else { return dp[0][n] }
guard n > 0 else { return false }
for i in 1...m {
for j in 1...n {
if pArr[j - 1] == "*" {
let zeroOccurrence = dp[i][j - 2]
let precedingChar = pArr[j - 2]
let matchesCurrentChar = precedingChar == "." || precedingChar == sArr[i - 1]
dp[i][j] = zeroOccurrence || (matchesCurrentChar && dp[i - 1][j])
} else {
let matchesCurrentChar = pArr[j - 1] == "." || pArr[j - 1] == sArr[i - 1]
dp[i][j] = matchesCurrentChar && dp[i - 1][j - 1]
}
}
}
return dp[m][n]
}
// smoke test — same cases as the brute force
print(isMatch("aa", "a")) // false
print(isMatch("aa", "a*")) // true
print(isMatch("ab", ".*")) // true
print(isMatch("aab", "c*a*b")) // trueBig-O: O(m · n) time — every cell is filled exactly once from at most two already-known neighbors. O(m · n) space for the dp table.
Both versions handle * the same way — try skipping the starred element entirely, or consuming one more copy of it — but the brute force treats every (i, j) as fresh no matter how many branches arrive at it, so the same position pairs are re-solved exponentially many times, especially with chained * groups. The optimal version fills the table row by row, so dp[i][j-2] (zero occurrences), dp[i-1][j] (one more occurrence), and dp[i-1][j-1] (plain character match) are always already-finished answers by the time dp[i][j] needs them. Reusing those already-solved neighbors instead of re-branching on every * from scratch is what turns exponential wildcard matching into a flat O(m · n) table fill.
-
2D Dynamic Programming — a two-string-index table like Edit Distance or Interleaving String, but with a special branching rule whenever the pattern's current character is
*. -
Arrays and Strings — both
sandpare converted to[Character]arrays for O(1) indexed access, anddpis a plain 2-D boolean array.
Regex Matching is 2-D DP with one extra rule: a * lets a cell look sideways two columns (skip the starred pair) as well as up one row (reuse the starred character), instead of only ever looking diagonally.
- Why does the "one more occurrence" branch (
dp[i - 1][j]) keepjunchanged rather than moving toj + 1orj - 1? What does staying on the same pattern position represent? - Trace
isMatch("aa", "a*")by hand-filling the small3 x 3table. Which two cells doesdp[2][2]end up depending on, and which one supplies thetrue? - Why must
dp[0][j]for the empty-string row be computed left to right usingdp[0][j-2], rather than just beingfalsefor everyj > 0? Give a concrete pattern wheredp[0][j]istruefor somej > 0.