LeetCode 正則表達式匹配：從暴力遞歸到動態規劃優化

時間複雜度最壞呈指數級，空間複雜度為遞歸棧深度 O(n)。

public boolean isMatch(String s, String p) {
    return helper(s, p, 0, 0);
}
private boolean helper(String s, String p, int i, int j) {
    if (j == p.length()) return i == s.length();
    if (j == p.length()-1 || p.charAt(j+1) != '*') {
        if (i == s.length() || (s.charAt(i) != p.charAt(j) && p.charAt(j) != '.')) return false;
        return helper(s, p, i+1, j+1);
    }
    // p.charAt(j+1) == '*'
    while (i < s.length() && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))) {
        if (helper(s, p, i, j+2)) return true;
        i++;
    }
    return helper(s, p, i, j+2);
}

動態規劃優化

定義 dp[i][j] 表示 s 前 i 字符與 p 前 j 字符是否匹配（維度 (n+1)×(m+1)）。外層循環遍歷模式 p，內層遍歷字串 s，避免重複計算。

• p[j-1] != '*'：dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.')
• p[j-1] == '*' 且 p[j-2] != '.'：滿足以下任一即為 true：
  1. dp[i][j-2]（* 匹配 0 次）
  2. dp[i-1][j] && s[i-1]==p[j-2]（* 匹配 ≥1 次）
• p[j-1] == '*' 且 p[j-2] == '.'：.* 可匹配任意子串，若 dp[i][j-2] 或 dp[i-1][j] 為 true，則後續同列全為 true。

時間/空間複雜度均為 O(n²)。

public boolean isMatch(String s, String p) {
    if (s.isEmpty() && p.isEmpty()) return true;
    if (p.isEmpty()) return false;
    boolean[][] dp = new boolean[s.length()+1][p.length()+1];
    dp[0][0] = true;
    for (int j = 0; j < p.length(); j++) {
        if (p.charAt(j) == '*') {
            if (j > 0 && dp[0][j-1]) dp[0][j+1] = true;
            if (j < 1) continue;
            if (p.charAt(j-1) != '.') {
                for (int i = 0; i < s.length(); i++) {
                    if (dp[i+1][j] || (j>0 && dp[i+1][j-1]) ||
                        (i>0 && j>0 && dp[i][j+1] && s.charAt(i)==s.charAt(i-1) && s.charAt(i-1)==p.charAt(j-1)))
                        dp[i+1][j+1] = true;
                }
            } else {
                int i = 0;
                while (j>0 && i

總結
動態規劃通過備份中間結果將指數級遞歸降為多項式複雜度，是面試中常考的硬核題目。類似思路可應用於 Wildcard Matching 等變體。