今天來講第10題

題目

題目講解

回傳給予的字串 (s) 是否可成功對應 使用了 '.' 和'*' 的正規表達式regular expression 的模板字串 (p):

• '.' 可對應任何字元
• '*' 對應0或多個在這之前的某字元
  且套用需整個字串可以套用在整個模板字串, 不可只有部分字串套用成功

解題思路

1. 初始化動態規劃表 (dp table)：

   • 創建一個大小為 (m+1) * (n+1) 的二維陣列 dp[m+1][n+1]，其中 m 是字串 s 的長度，n 是模式 p 的長度。
   • dp[i][j] 表示 s[0..i-1] 和 p[0..j-1] 是否匹配。
   • 設定 dp[0][0] = true，表示空字串與空模式相匹配。
   • 處理模式中出現的 *：如果模式的形式像 a* 或 .*，那麼這可以匹配空字串，因此可以設置 dp[0][j] = dp[0][j-2]。

2. 遍歷字串 s 和模式 p：

   • 使用雙重迴圈，外層遍歷字串 s，內層遍歷模式 p。遍歷時，對於每個字元 s[i-1] 和模式 p[j-1]，需要處理三種匹配情況。

3. 處理匹配情況：

   • 情況 1：字元完全匹配或 . 匹配：

     • 如果 s[i-1] == p[j-1]，或者 p[j-1] == '.'（可以匹配任意單一字元），則 dp[i][j] = dp[i-1][j-1]。也就是說，當前字元匹配後，取決於之前的匹配情況。

   • 情況 2：模式中出現 *：

     • * 可以匹配前一個字元零次或多次。
     • 匹配 0 次：忽略掉 * 和它前面的字元，對應 dp[i][j] = dp[i][j-2]。
     • 匹配多次：如果 s[i-1] == p[j-2]（或 p[j-2] == '.'），則可以進一步匹配前一個字元，對應 dp[i][j] = dp[i-1][j]。

   • 情況 3：無匹配：

     • 如果當前字元 s[i-1] 與模式 p[j-1] 無法匹配，則 dp[i][j] = false。

4. 最終結果：

   • 當雙重迴圈結束後，dp[m][n] 即為結果，表示字串 s 和模式 p 是否完全匹配。

code

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        // 初始化 dp table, 空字串與空模式是匹配的
        dp[0][0] = true;

        // 處理像 "a*" 這樣的模式，這種情況可以匹配空字串
        for (int j = 2; j <= n; j += 2) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填充 dp table
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '.' || s[i - 1] == p[j - 1]) {
                    // 當字元匹配，或當模式為 '.' 時，繼承上一匹配狀態
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    // '*' 的情況，判斷是否可以讓前一個字元重複 0 次或者多次
                    dp[i][j] = dp[i][j - 2];  // '*' 代表前一個字元出現 0 次
                    if (p[j - 2] == '.' || s[i - 1] == p[j - 2]) {
                        // 前一個字元與當前匹配，可以繼承 dp[i-1][j]
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
};