題目網址：https://leetcode.cn/problems/regular-expression-matching/

題意：給你一個 string s 和一個 string pattern p，請實現一個支持 '.' 和 '*' 的正則表達式匹配。

  • '.' 匹配任意單個 char
  • '*' 匹配 0 個 or 多個前面的那一個元素

所謂匹配, 是要涵蓋整個 s 的, 而不是部分 string。

Solution：

想法：利用 DP, 其中 dp[i][j] 判斷 s[0 ~ (i - 1)] 和 p[0 ~ (j - 1)] 是否匹配，每次判斷當前 s、p 的最後一個 char 是否匹配

  • 若 s[i - 1] == p[j - 1] 或 p[j - 1] == '.' : 代表當前 s、p 的最後一個 char 匹配, 則當前 s、p 是否匹配取決於前面的 substring, 也就是說 dp[i][j] = dp[i - 1][j - 1]
  • 若 p[j - 1] == '*' : 代表要看 p[j - 1] 的前一個 char p[j - 2]

    • 若 s[i - 1] == p[j - 2] 或 p[j - 2] == '.' : 代表當前 s、p 最後一個 char 是匹配的, 則 `` 分别可重覆 0 次 or 重覆 1 次 or 重覆 2 次以上

      • 重覆 0 次 : s[i - 1] 要和 p[j - 3] 比較 ➔ dp[i][j] = dp[i][j - 2]

      • 重覆 1 次 : s[i - 2] 要和 p[j - 3] 比較 ➔ dp[i][j] = dp[i - 1][j - 2]

      • 重覆 2 次以上 : s 去掉最後一個 char, 而 p 不動➔ dp[i][j] = dp[i - 1][j]

    • 若 s[i - 1] != p[j - 2] : 當前 s、p 最後一個 char 不匹配, 則 `` 重覆 0 次。s 不動, p 要往前取看是否匹配 ➔ dp[i][j] = dp[i][j - 2]

除此之外, 還要考慮邊界條件

  • 當 s、p 皆為空時, 兩者匹配
  • 當 s 為空, 且 p 不為空時, 兩者卻匹配的情況。e.g. s = "", p = "a*a*a*"
class Solution {
public:
    bool isMatch(string s, string p) {
        const int m = s.size();
        const int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        // s、p 皆為空, 兩者匹配
        dp[0][0] = true;

        // s 為空, p 不為空, 但 s、p 匹配的情況, e.g. s = "", p = "a*a*a*"
        for (int j = 1; j <= n; ++j) {
            // j = 1 時, p[j - 1] 必不為 `*`, 因此不會執行到 dp[0][j - 2] 導致越界
            dp[0][j] = (p[j - 1] == '*') && dp[0][j - 2];
        }

        // dp[i][j] : 判斷 s[0 ~ (i - 1)]、p[0 ~ (j - 1)] 是否匹配
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 若 s[i - 1]、p[j - 1] 匹配
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                        // * 分别是重覆 0 次 or 重覆 1 次 or 重覆 2 次以上
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    } else { // s[i - 1] != p[j - 1], 則 * 重複 0 次
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }

        return dp[m][n];
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(m \cdot n)$ ➔ dp