Implement regular-expression matching with '.' (any single character) and '*' (zero or more of the preceding element). The match must cover the entire string s.
dp[i][j] = do the first i chars of s match the first j of p? For 'x*' at p[j−2..j−1]: zero copies (dp[i][j−2]) or one more copy (dp[i−1][j] if s[i−1] matches x). Otherwise match the single char diagonally.
1function isMatch(s: string, p: string): boolean {2const m = s.length, n = p.length;3const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));4dp[0][0] = true;5const eq = (i: number, j: number) => p[j - 1] === "." || p[j - 1] === s[i - 1];6for (let i = 0; i <= m; i++)7for (let j = 1; j <= n; j++)8dp[i][j] = p[j - 1] === "*"9? dp[i][j - 2] || (i > 0 && eq(i, j - 1) && dp[i - 1][j])10: i > 0 && eq(i, j) && dp[i - 1][j - 1];11return dp[m][n];12}
| ∅ | c | * | a | * | b | |
|---|---|---|---|---|---|---|
| ∅ | T | |||||
| a | · | |||||
| a | · | |||||
| b | · |
Empty matches empty.
Space: play/pause · ←/→: step