LeetCode Regular Expression Matching：遞歸與動態規劃兩種解法

題目簡介

實現正則匹配：模式串 p 中 '.' 匹配任意單字符，'*' 匹配前一字符 0 次或多次。需完全匹配整個文本串 s。例如 isMatch("aa", "a*") = true，isMatch("aab", "c*a*b") = true。

解法一：遞歸

關鍵處理 '*'：若 p[1]=='*'，則 '*' 可代表 0 個、1 個、2 個... p[0]。嘗試所有可能：先跳過 '*'（0 個），或若 s[0] 匹配 p[0] 則消耗 s[0] 遞歸。代碼簡潔但可能重複計算。

解法二：動態規劃

定義 dp[i][j] 表示 s[0..i-1] 與 p[0..j-1] 是否匹配。轉移：

• 若 p[j-1] != '*'：dp[i][j] = dp[i-1][j-1] && match(s[i-1], p[j-1])。
• 若 p[j-1] == '*'：dp[i][j] = dp[i][j-2] || (match(s[i-1], p[j-2]) && dp[i-1][j])。前者為 '*' 匹配 0 個，後者為匹配至少 1 個（利用 dp[i-1][j] 已包含多個情況）。

初始化：dp[0][0]=true；dp[0][j] 僅當 p[j-1]=='*' 且 dp[0][j-2] 為真。

代碼實現

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
    dp[0][0] = true;
    for (int j = 1; j <= n; j++)
        dp[0][j] = (j>1 && p[j-1]=='*' && dp[0][j-2]);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (p[j-1] != '*')
                dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
            else
                dp[i][j] = dp[i][j-2] || ((s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j]);
    return dp[m][n];
}

複雜度分析

遞歸最坏指數級，DP 時間空間均 O(mn)，穩定高效。