LeetCode 10 Regular Expression Matching：正則表達式匹配

題目描述

實現支援 '.' 與 '*' 的正則匹配。'.' 匹配任意單字符，'*' 匹配前一元素 0 次或多次。匹配需覆蓋整個輸入字串。函數原型：bool isMatch(const char* s, const char* p)。

遞歸解法

模式串 p 分情況：

1. p 為空 → s 也為空才匹配。
2. p 長度 1 → s 長度 1 且字符匹配（或 p[0]=='.'）。
3. p[1] != '*' → 首字符匹配且遞歸匹配剩餘。
4. p[1] == '*' → 兩種可能：* 匹配 0 次（跳過 p[0]* 遞歸），或匹配 ≥1 次（首字符匹配且 s 推進一位遞歸）。

Java 實現

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        if (p.length() == 1) return s.length() == 1 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
        if (p.charAt(1) != '*') {
            if (s.isEmpty()) return false;
            return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
        } else {
            while (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
                if (isMatch(s, p.substring(2))) return true;
                s = s.substring(1);
            }
            return isMatch(s, p.substring(2));
        }
    }
}

優化方向

• 記憶化遞歸（DP）避免重複子問題，時間 O(MN)。
• 動態規劃底-up 表填充。