題目描述:給定字串 s 和模式 p,實作支援 '?' 和 '*' 的萬用字元比對。'?' 可匹配任意單一字元,'*' 可匹配任意序列(包含空字串)。判斷 s 是否與 p 完全匹配。
解題思路:使用二維動態規劃。定義 dp[i][j] 表示 s 的前 i 個字元是否能被 p 的前 j 個字元完整匹配。
轉移規則如下:
p[j-1] == '*':'*' 可以匹配空字串(沿用 dp[i][j-1]),也可以多吞一個字元(沿用 dp[i-1][j]),因此 dp[i][j] = dp[i][j-1] || dp[i-1][j]。p[j-1] == '?' 或 p[j-1] == s[i-1](字元相等):dp[i][j] = dp[i-1][j-1]。dp[i][j] = false。邊界條件:dp[0][0] = true(空字串匹配空模式);若模式開頭連續為 '*',則 dp[0][j] = true,因為 '*' 可全部匹配空字串。最終答案為 dp[m][n](m = s.size(), n = p.size())。
時間複雜度:O(m × n) — 需填滿大小為 (m+1) × (n+1) 的 DP 表,其中 m = |s|、n = |p|,每格計算為 O(1)。
空間複雜度:O(m × n) — 儲存整張 DP 表。若使用滾動陣列(只保留前一行),可降至 O(n)。
1. Let m = len(s), n = len(p).
2. Create (m+1) x (n+1) boolean table dp, initialized to false.
3. Set dp[0][0] = true (empty matches empty).
4. For j from 1 to n: if p[j-1] == '*', set dp[0][j] = dp[0][j-1].
5. For i from 1 to m:
a. For j from 1 to n:
- If p[j-1] == '*': dp[i][j] = dp[i][j-1] OR dp[i-1][j]
- Else if p[j-1] == '?' OR p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]
- Else: dp[i][j] = false
6. Return dp[m][n].方法一:貪心 + 雙指標
使用 si(指向 s)、pi(指向 p)和 starPos(最近一個 '*' 在 p 中的位置)、matchPos('*' 匹配到 s 的位置)逐字元掃描。若遇到 '*' 記錄位置並繼續;若字元不匹配且之前有 '*',回溯讓 '*' 多吞一個字元。時間複雜度 O(m × n) 最壞、O(m + n) 平均,空間複雜度 O(1)。
方法二:遞迴 + 記憶化
定義遞迴函數 solve(i, j) 表示 s[i..] 是否匹配 p[j..]。使用 unordered_map 或二維陣列儲存已計算結果避免重複計算。時間複雜度 O(m × n),空間複雜度 O(m × n)(遞迴棧加 memo 表)。本質上與 DP 等價,但 top-down 方式在稀疏狀態下可能更快。
'*' 數量有限制(例如最多 k 個),演算法的時間複雜度會如何改變?是否有更快的解法?