Description
實作正則表達式匹配，支援
.（匹配任意單一字元）和*（匹配零個或多個前一個字元）。匹配需要覆蓋整個字串。
Example:
Input: s = “aab”, p = “cab” Output: true (c* 匹配零個 c, a* 匹配兩個 a, b 匹配 b)
Intuition#
*不會單獨出現，總是跟在某個字元後面形成「x*」的組合- 兩種情況：
p[j-1]不是*：直接比較s[i-1]和p[j-1]p[j-1]是*：- 匹配零次：
dp[i][j] = dp[i][j-2]（跳過「x*」） - 匹配一次以上：
dp[i][j] = dp[i-1][j]（前提是 s[i-1] 匹配 p[j-2]）
- 匹配零次：
Approaches#
1: 遞迴 + 記憶化#
- 概念: 從頭開始匹配，遇到
*時分支處理，用 memo 快取結果。 - 時間複雜度:
O(m * n) - 空間複雜度:
O(m * n)
class Solution {
fun isMatch(s: String, p: String): Boolean {
val memo = Array(s.length + 1) { arrayOfNulls<Boolean>(p.length + 1) }
return dp(s, p, 0, 0, memo)
}
private fun dp(s: String, p: String, i: Int, j: Int, memo: Array<Array<Boolean?>>): Boolean {
if (memo[i][j] != null) return memo[i][j]!!
val result: Boolean
if (j == p.length) {
result = i == s.length
} else {
val firstMatch = i < s.length && (p[j] == '.' || s[i] == p[j])
result = if (j + 1 < p.length && p[j + 1] == '*') {
dp(s, p, i, j + 2, memo) || (firstMatch && dp(s, p, i + 1, j, memo))
} else {
firstMatch && dp(s, p, i + 1, j + 1, memo)
}
}
memo[i][j] = result
return result
}
}⭐2: Bottom-Up DP#
- 概念: 建立
(m+1) x (n+1)的表格，從後往前或從前往後填寫。 - 時間複雜度:
O(m * n) - 空間複雜度:
O(m * n)
class Solution {
fun isMatch(s: String, p: String): Boolean {
val m = s.length
val n = p.length
val dp = Array(m + 1) { BooleanArray(n + 1) }
dp[0][0] = true
// 處理 p 的前綴匹配空字串（如 a*, a*b*, ...）
for (j in 2..n) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 2]
}
}
for (i in 1..m) {
for (j in 1..n) {
if (p[j - 1] == '*') {
// 匹配零次
dp[i][j] = dp[i][j - 2]
// 匹配一次以上
if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j]
}
} else {
if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1]
}
}
}
}
return dp[m][n]
}
}🔑 Takeaways#
- Pattern: 字串匹配 DP — 處理特殊匹配符號的轉移邏輯
- 關鍵技巧:
*的關鍵是「匹配零次 vs 一次以上」的分支；初始化時要處理a*b*這種能匹配空字串的 pattern