解題說明
Wildcard Matching
題目描述：給定字串 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()）。
C++ 解法
複雜度分析
時間複雜度：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 方式在稀疏狀態下可能更快。
延伸思考
- 若模式 p 中的
'*'數量有限制（例如最多 k 個），演算法的時間複雜度會如何改變？是否有更快的解法？ - 如何修改演算法以支援「最長匹配子字串」，即找出 s 中最長且能被 p 匹配的子字串？
- 若 s 和 p 的長度都非常大（例如 10^6），O(m × n) 的 DP 會超時，有哪些方法可以加速（例如 SIMD 位元平行化、稀疏 DP 或分治法）？