LeetCode 10. 正則表達式匹配：遞歸與動態規劃雙解法深度解析

LeetCode 10. 正則表達式匹配：遞歸與動態規劃雙解法深度解析

實現支持 . 和 * 的正則匹配，是經典的字符串動態規劃問題。本文提供遞歸回溯與 DP 兩種解法，並分析 .* 處理的難點。

題目要求

• . 匹配任意單字符
• * 匹配前一字符 0 次或多次
• 匹配必須覆蓋整個輸入字符串

核心測試用例

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

解法一：遞歸回溯（直觀但指數級）

核心思路：逐字符匹配，遇到 * 時嘗試 0 次、1 次、多次匹配；遇到 .* 時遞歸嘗試所有可能分割點。

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

private boolean match(String s, String p, int i, int j) {
    // 模式串耗盡
    if (j == p.length()) return i == s.length();

    // 判斷下一字符是否為 *
    boolean hasStar = (j + 1 < p.length() && p.charAt(j + 1) == '*');
    char pc = p.charAt(j);

    if (hasStar) {
        // 情況 1：* 匹配 0 次，直接跳過 "x*"
        if (match(s, p, i, j + 2)) return true;
        
        // 情況 2：* 匹配 1 次或多次，需當前字符匹配
        if (i < s.length() && (pc == '.' || pc == s.charAt(i))) {
            return match(s, p, i + 1, j); // 關鍵：j 不動，繼續用 * 匹配更多
        }
        return false;
    } else {
        // 無 *：單字符匹配
        if (i < s.length() && (pc == '.' || pc == s.charAt(i))) {
            return match(s, p, i + 1, j + 1);
        }
        return false;
    }
}

缺點：重複子問題導致指數級時間，.* 情況下極慢。

解法二：動態規劃（標準 O(mn) 解）

dp[i][j] 表示 s[i:] 與 p[j:] 是否匹配。從後向前填表。

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[m][n] = true; // 空匹配空

    for (int i = m; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            boolean firstMatch = (i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));
            
            if (j + 1 < n && p.charAt(j + 1) == '*') {
                // * 匹配 0 次 或 1+ 次
                dp[i][j] = dp[i][j + 2] || (firstMatch && dp[i + 1][j]);
            } else {
                dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
    }
    return dp[0][0];
}

關鍵難點：.* 的處理

.* 可匹配任意長度字符串。DP 中 dp[i][j] = dp[i][j+2] || (firstMatch && dp[i+1][j]) 完美建模：

• dp[i][j+2]：.* 匹配 0 字符，直接跳過
• firstMatch && dp[i+1][j]：匹配 1 字符，j 不變 允許繼續匹配更多

複雜度分析

空間優化：滾動數組 O(n)

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[] dp = new boolean[n + 1];
    dp[n] = true;
    
    for (int i = m; i >= 0; i--) {
        boolean[] next = new boolean[n + 1];
        next[n] = (i == m);
        for (int j = n - 1; j >= 0; j--) {
            boolean first = (i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));
            if (j + 1 < n && p.charAt(j + 1) == '*') {
                next[j] = next[j + 2] || (first && dp[j]);
            } else {
                next[j] = first && dp[j + 1];
            }
        }
        dp = next;
    }
    return dp[0];
}

總結

• 遞歸思路清晰但性能不可控，面試可先寫遞歸再優化 DP
• DP 狀態定義：dp[i][j] 為後綴匹配問題
• * 的狀態轉移是核心：dp[i][j] = dp[i][j+2] || (match && dp[i+1][j])
• 注意邊界：i == m 時 firstMatch = false，但 * 仍可匹配 0 次