LeetCode Regular Expression Matching 正則表達式匹配 (遞歸 + 回溯)

問題

實現支持 '.' 和 '*' 的正則匹配：'.' 匹配任意單字符，'*' 匹配前一字符 0 次或多次。需完全匹配整個字符串。

遞歸思路

函數 `match(s, p)`：
- 若 p 為空，返回 s 是否為空。
- 若 p 第二字符不是 '*'：首字符匹配則遞歸匹配剩餘。
- 若 p 第二字符是 '*'：兩種選擇：
1. 忽略 "x*" (匹配 0 次) → `match(s, p.substr(2))`
2. 首字符匹配且 s 非空 → `match(s.substr(1), p)` (保留 '*' 繼續匹配)

代碼 (C++)

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        bool firstMatch = !s.empty() && (p[0] == s[0] || p[0] == '.');
        if (p.size() >= 2 && p[1] == '*') {
            return isMatch(s, p.substr(2)) || (firstMatch && isMatch(s.substr(1), p));
        } else {
            return firstMatch && isMatch(s.substr(1), p.substr(1));
        }
    }
};

優化：動態規劃 / 記憶化

遞歸有重疊子問題，用 `dp[i][j]` 表示 s[i:] 和 p[j:] 是否匹配，自底向上填表或記憶化遞歸，時間 O(mn)。

關鍵測試用例

• `isMatch("aa", "a*") → true`
• `isMatch("ab", ".*") → true`
• `isMatch("aab", "c*a*b") → true` (c* 匹配 0 次)