44. 通配符匹配

思路

先不去考慮 "$?$"、"$*$" 的情況，單純只看兩個字串能不能相同。 這時如果滿足以下兩個條件：

1. $s$ 的前 $i-1$ 個字元跟 $p$ 的前 $i-1$ 個字元都相同。
2. $s[i] = p[i]$。
3. 那麼 $s$ 的前 $i$ 個字元跟 $p$ 的前 $i$ 個字元相同，不滿足條件則不同。

令 $m = s.length$，$n = p.length$，我們要求的就是「$s$ 的前 $m$ 個字元跟 $p$ 的前 $n$ 個字元」是否相同。
轉成動態規劃的表達形式，$dp[i][j]$ 代表「$s$ 的前 $i$ 個字元跟 $p$ 的前 $j$ 個字元是否相同」。

假如考慮進 "$?$" 的情況，它能取代任意字元。
上面的第二個條件就變成了$s[i] = p[i] || p[i] ==$ "$?$"，其餘都相同。

再考慮進 "$*$" 的情況，它可以取代任意數量的字元，可以是 $0$ 個、$1$ 個、$2$ 個……。

• 取代 $0$ 個：$dp[i][j - 1]$
• 取代 $1$ 個：$dp[i - 1][j - 1]$
• 取代 $2$ 個：$dp[i - 2][j - 1]$

只需要滿足一種情況，$dp[i][j]$ 就會是true。
但這不代表要一個個檢查，那會花很多時間，可以用前面算好的去簡化。
假設$p[j]$是"$*$"，

• 把它當空字串：$dp[i][j - 1]$
• 把它當任意字串：$dp[i - 1][j]$

因為每次只會用到上一排的數值，能藉此壓縮空間複雜度，丟掉一個維度。

用到的有 $dp[i - 1][j - 1]$、$dp[i][j - 1]$、$dp[i - 1][j]$這三個，

因為需要 $dp[i][j - 1]$，所以得從左到右更新。

$dp[i][j - 1]$、$dp[i - 1][j]$ 則是需要舊有的資料，

只有用一維陣列，得事先存下 $dp[i - 1][j - 1]$。

最後，如果沒有更新數值，需要填上false，避免舊有資料殘留。

程式碼

1. 動態規劃

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true; // 空字串和空字串是一樣的
        for(int j = 1; j <= n; ++j) {
            if(p[j] == '*') f[0][j] = true; // 空字串只能跟 * 搭配
            else break;
        }
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                // 前面可以匹配，並且數字相同。
                if(f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?')){
                    f[i][j] = true;
                }
                // 這一格是 '*'，它可以作為空字串。
                else if(p[j] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1];
                }
            }
        }
        return f[m][n];
    }
};

2. 狀態壓縮

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        vector<bool> f(n + 1, false);
        f[0] = true; // 空字串和空字串是一樣的
        for(int j = 1; j <= n; ++j) {
            if(p[j] == '*') f[j] = true; // 空字串只能跟 * 搭配
            else break;
        }
        for(int i = 1; i <= m; ++i) {
            bool prev = f[0]; // f[i - 1][0]
            f[0] = false; // f[i][0] 除了初始化都是 false
            for(int j = 1; j <= n; ++j) {
                int temp = f[j]; // f[i - 1][j]
                if(prev && (s[i] == p[j] || p[j] == '?')){
                    f[j] = true;
                }
                else if(p[j] == '*') {
                    f[j] = f[j] || f[j - 1];
                }
                else {
                    // 沒更新，用 false 覆蓋，避免舊資料殘留
                    f[j] = false;
                }
                prev = temp; // f[i - 1][j]會變成下次的 f[i - 1][j - 1]
            }
        }
        return f.back();
    }
};

複雜度分析

• 時間複雜度：$O(mn)$
• 空間複雜度：$O(mn)$，能壓縮到$O(n)$