Implement regular expression matching for a string s and a pattern p that supports two special characters: . matches any single character, and * matches zero or more copies of the character just before it. The pattern must match the whole string, not just a part of it. Return true or false.
c* takes zero c, a* takes "aa", then b.- 1 <= s.length <= 20
- 1 <= p.length <= 20
- `s` has lowercase letters; `p` has lowercase letters, `.` and `*`
- Every `*` has a valid character before it
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Plain recursion branches at every * and can take exponential time, because the same (i, j) pair is reached many ways. State: dp[i][j] is true if the suffix s[i:] matches the suffix p[j:]. Let first mean i < len(s) and p[j] is s[i] or .. Recurrence: if p[j+1] is *, then dp[i][j] = dp[i][j+2] (use zero copies) or first and dp[i+1][j] (eat one character, keep the star). Otherwise dp[i][j] = first and dp[i+1][j+1]. Base case: dp[len(s)][len(p)] = true: empty matches empty. Note that i runs up to len(s) itself, because a pattern like a* can match an empty suffix.
Algorithm
- Make a
(m+1) x (n+1)table of false and setdp[m][n] = true. - Loop
ifrommdown to 0 andjfromn - 1down to 0. - Compute
first = i < m and p[j] in (s[i], "."). - If
j + 1 < nandp[j+1] == "*":dp[i][j] = dp[i][j+2] or (first and dp[i+1][j]). Elsedp[i][j] = first and dp[i+1][j+1]. - Return
dp[0][0].
O(m * n)Space: O(m * n)x* may match zero characters, so s = "aab", p = "c*a*b" fails. Another trap: the loop over i must include i = m (empty rest of s) or patterns like a*b* against an empty suffix break.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[i][j]: s[i:] matches p[j:] dp[m][n] = True for i in range(m, -1, -1): for j in range(n - 1, -1, -1): first = i < m and p[j] in (s[i], ".") if j + 1 < n and p[j + 1] == "*": # zero copies of p[j], or eat one char and keep the star dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j]) else: dp[i][j] = first and dp[i + 1][j + 1] return dp[0][0]