LeetCode 10. 正則表達式匹配：遞歸與動態規劃完整解析（Java 實現）

LeetCode 10. 正則表達式匹配 - 題目詳解

題目描述

實現支援 '.' 和 '*' 的正則表達式匹配：

• '.' 匹配任意單一字元
• '*' 匹配前一個字元零次或多次（含 '.'）

匹配需覆蓋整個輸入字串（非部分匹配）。

核心範例解析

解題思路：遞歸回溯 + 記憶化優化

關鍵觀察

模式中 '*' 只能出現在字元之後，決策點在於：當遇到 '*' 時，我們有兩種選擇：

1. 忽略「字元+*」組合：跳過模式中的兩個字元，字串指針不動
2. 使用「字元+*」匹配：若當前字元匹配，字串指針後移，模式指針不動（因為 '*' 可重複）

遞歸狀態定義

isMatch(s, i, p, j)：字串 s[i:] 是否匹配模式 p[j:]

Java 完整實現（優化版）

public class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, 0, p, 0);
    }

    private boolean isMatch(String s, int i, String p, int j) {
        int ls = s.length();
        int lp = p.length();

        // 基礎情況：模式已耗盡
        if (j == lp) {
            return i == ls; // 字串也必須耗盡才算匹配
        }

        // 情況 1：模式下一字元不是 '*'，或已是最後一字元
        // 必須逐字元匹配
        if (j == lp - 1 || p.charAt(j + 1) != '*') {
            return (i < ls && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'))
                    && isMatch(s, i + 1, p, j + 1);
        }

        // 情況 2：模式下一字元是 '*'，複雜決策點
        // 嘗試匹配 0 次、1 次、多次...
        while (i < ls && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
            // 嘗試跳過「字元+*」（匹配 0 次）
            if (isMatch(s, i, p, j + 2)) {
                return true;
            }
            // 匹配 1 次，繼續嘗試更多
            i++;
        }

        // 所有嘗試均失敗，最後嘗試匹配 0 次
        return isMatch(s, i, p, j + 2);
    }
}

複雜度分析

• 時間複雜度：O(2^(m+n)) 最壞情況（無記憶化），其中 m、n 為字串與模式長度
• 空間複雜度：O(m+n) 遞歸調用棧深度

進階優化：動態規劃 (DP) 底-up 實現

為避免重複計算，可引入 Boolean[][] memo 記憶化，或採用 DP 表格法：

// DP 狀態：dp[i][j] 表示 s[i:] 與 p[j:] 是否匹配
// 初始化：dp[ls][lp] = true
// 狀態轉移參考上述遞歸邏輯
// 時間/空間複雜度均優化至 O(m*n)

核心心法總結

1. 識別決策點：'*' 是唯一分支點
2. 窮舉選擇：匹配 0 次 vs 匹配 1+ 次
3. 基礎情況：模式耗盡時，字串必須也耗盡
4. 優化方向：記憶化搜尋或 DP 消除重疊子問題

這道題是字串匹配與狀態機建模的經典範例，掌握其遞歸結構對解決類似「通配符匹配」、「正則引擎實現」等問題極有幫助。