LeetCode 10：正則表達式匹配 — 遞歸回溯完整解析

題目

實現支持 '.' 和 '*' 的正則匹配：

• '.' 匹配任意單字符。
• '*' 匹配前一字符 0 次或多次。
• 匹配需覆蓋整個輸入字符串（非部分）。

範例

isMatch("aa","a")   → false
isMatch("aa","a*")  → true
isMatch("ab",".*")  → true
isMatch("aab","c*a*b") → true

遞歸回溯三大分支

設字符串索引 i，模式索引 j。

1. 模式結束：p[j]=='\0' → 返回 s[i]=='\0'。
2. 下一字符非 '*'：p[j+1]!='*' → 單字符匹配：
   (s[i]==p[j] || (p[j]=='.' && s[i]!='\0')) && match(i+1, j+1)。
3. 下一字符是 '*'：p[j+1]=='*' → 嘗試 k=0..剩餘長度：
   while (匹配) { if (match(i, j+2)) return true; i++; }
return match(i, j+2);
   （j+2 跳過 x*，i 逐步增加表示 * 匹配多次）

C++ 代碼

class Solution {
public:
    bool isMatch(string s, string p) {
        return match(s, p, 0, 0);
    }
private:
    bool match(const string& s, const string& p, int i, int j) {
        if (j == p.size()) return i == s.size();
        if (j + 1 < p.size() && p[j+1] == '*') {
            // 情況 3：x*
            while (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (match(s, p, i, j+2)) return true;
                ++i;
            }
            return match(s, p, i, j+2);  // x* 匹配 0 次
        } else {
            // 情況 2：單字符
            if (i < s.size() && (s[i] == p[j] || p[j] == '.'))
                return match(s, p, i+1, j+1);
            return false;
        }
    }
};

動態規劃優化（自底向上）

dp[i][j] 表示 s[i:] 與 p[j:] 是否匹配。時間空間 O(mn)，避免重複子問題計算。

複雜度

• 遞歸：最壞 O(2^{m+n})，實際有大量剪枝，LeetCode 通過。
• DP：O(mn) 時間空間，穩健。

關鍵點

1. * 只能跟在有效字符後，不會出現開頭 *。
2. 遞歸終止條件須嚴格判斷 i == s.size()。
3. .* 可匹配任意字符串（含空），是最強模式。