解題說明
Regular Expression Matching（正則表達式匹配）
題目描述：給定字串 s 和模式 p，實作支援 . 和 * 的正則表達式匹配。. 匹配任意單一字元；* 匹配前一個元素零次或多次。要求判斷 p 是否能匹配整個字串 s（而非部分匹配）。
解題思路：
定義 dp[i][j] 為 s[0..i-1] 是否能被 p[0..j-1] 匹配。
狀態轉移（分三種情況）：
情況一：p[j-1] 是普通字元（非 . 非 *）
dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]
情況二：p[j-1] == '.'
.匹配任意字元：dp[i][j] = dp[i-1][j-1]
情況三：p[j-1] == '*'（* 不能出現在 p 的開頭，保證前一位存在）
- 用 0 次：
x*整體消除，dp[i][j] = dp[i][j-2] - 用 1+ 次：前一字元
p[j-2]必須能匹配s[i-1]，即p[j-2]=='.' || p[j-2]==s[i-1]，此時dp[i][j] = dp[i-1][j]（s消耗一個字元，模式繼續匹配） - 兩種取 OR：
dp[i][j] = dp[i][j-2] || (match && dp[i-1][j])
邊界條件：
dp[0][0] = true（空字串匹配空模式）dp[0][j]：只有形如a*b*c*的模式才能匹配空字串，需特別處理（*用 0 次）
C++ 解法
複雜度分析
時間複雜度：O(m·n) — 雙層迴圈分別遍歷字串 s（長度 m）與模式 p（長度 n），每個格子計算為 O(1)，共需填滿 (m+1)×(n+1) 的表格。
空間複雜度：O(m·n) — 需要完整的二維 DP 表格。若使用滾動陣列可優化至 O(n)，但需額外保存 dp[i-1][j-1]（即 prev 變數），整體邏輯與 Edit Distance 的優化方式類似。
虛擬碼
1. Initialize dp[0..m][0..n] = false; dp[0][0] = true
2. Handle empty string base cases:
For j from 2 to n: if p[j-1]=='*': dp[0][j] = dp[0][j-2]
3. For i from 1 to m:
For j from 1 to n:
If p[j-1] == '*':
dp[i][j] = dp[i][j-2] (use zero times)
If p[j-2]=='.' OR p[j-2]==s[i-1]: (char before '*' matches current)
dp[i][j] = dp[i][j] OR dp[i-1][j] (use one more time)
Else:
charMatch = (p[j-1]=='.' OR p[j-1]==s[i-1])
dp[i][j] = charMatch AND dp[i-1][j-1]
4. Return dp[m][n]其他解法
遞迴 + 記憶化 O(m·n)：定義 match(i, j) 判斷 s[i..] 是否匹配 p[j..]，遇到 * 時遞迴嘗試 0 次或 1+ 次，用 memo[i][j] 快取。與迭代 DP 等價，但遞迴方向是由後往前，對某些人來說邏輯更自然。
NFA 模擬 O(m·n)：將正則模式建構為非確定性有限自動機（NFA），用集合追蹤所有可能的當前狀態，逐字元推進狀態集合。對於複雜正則引擎（支援更多語法）此方式更具擴展性，但對本題而言與 DP 複雜度相同。
延伸思考
- 若模式中還支援
+（一次或多次）和?（零次或一次），如何修改 DP 的狀態轉移？ - 本題與 LeetCode 44「Wildcard Matching」的差異在哪裡？
*的語義不同如何影響 DP 設計？ - 若字串
s非常長（如長度 10^6），有哪些優化策略可以加速正則匹配？