實作萬用字元比對：
?匹配任意單一字元，*匹配任意字元序列（含空字串）。判斷模式p是否能完整匹配字串s。與 10 正規表達式不同——這裡的*獨立成義，不依附前一字元。
Example:
Input: s = “aa”, p = ”*” → true Input: s = “cb”, p = “?a” → false Input: s = “adceb”, p = “ab” → true
Intuition
TIP
核心思路：二維 DP，dp[i][j] 表示 s 前 i 個字元能否被 p 前 j 個字元匹配。* 有兩種選擇：匹配空（dp[i][j-1]）或多吃一個 s 字元（dp[i-1][j]）。
dp[0][0] = true；dp[0][j]：只有 p 前綴全是*才為真p[j-1] == '*'→dp[i-1][j]（*再吃一個）或dp[i][j-1]（*配空）p[j-1] == '?'或字元相等 →dp[i-1][j-1]- 也有 O(1) 空間的貪心雙指針解（記住最後一個
*的位置以回溯）
Approaches
1. 2D DP — O(m·n) / O(m·n)
- Idea:
dp[i][j]=s[0..i)是否匹配p[0..j) - Time:
O(m·n) - Space:
O(m·n)（可滾動成O(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
for (j in 1..n) if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1]
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = when (p[j - 1]) {
'*' -> dp[i - 1][j] || dp[i][j - 1] // 吃一個 或 配空
'?' -> dp[i - 1][j - 1]
else -> dp[i - 1][j - 1] && s[i - 1] == p[j - 1]
}
}
}
return dp[m][n]
}
}⭐ 2. Greedy Two Pointers (backtrack to last *) — O(m·n) worst / O(1)
- Idea: 記住最後一個
*的位置與當時 s 的位置，不匹配時讓*多吃一個字元 - Time: 最差
O(m·n)，多數情況接近線性 - Space:
O(1)
class Solution {
fun isMatch(s: String, p: String): Boolean {
var i = 0; var j = 0
var starIdx = -1 // 最後一個 * 在 p 的位置
var match = 0 // 該 * 當時對齊的 s 位置
while (i < s.length) {
when {
j < p.length && (p[j] == '?' || p[j] == s[i]) -> { i++; j++ }
j < p.length && p[j] == '*' -> { starIdx = j; match = i; j++ }
starIdx != -1 -> { j = starIdx + 1; match++; i = match } // 回到 *，多吃一字元
else -> return false
}
}
while (j < p.length && p[j] == '*') j++ // 剩餘 p 必須全是 *
return j == p.length
}
}🔑 Takeaways
- Pattern: 字串比對 DP；
*的「配空 / 多吃一個」二選一是核心轉移 - Key trick: DP 寫法清晰好推；貪心雙指針靠「記住最後一個
*」回溯，達到 O(1) 空間。與 10 正規表達式比對對照——10 的*依附前字元，本題*獨立，轉移更簡單