題目

題目大意

有兩個字串 s, p，p 裡面可能含有 '?' 跟 '*'，其中 '?' 代表匹配一個任意字元、'*' 代表匹配任意字串(含空字串)，問字串 s 能否跟字串 p 匹配。

想法

在沒有 '*' 的情況，當字串 s 的前 i 個字元與字串 p 的 前 j 個字元匹配時，可以尋找字串 s 的第 i+1 個字元是否與字串 p 的第 j+1 個字元匹配。
有 '*' 的情況時，若字串 p 的第 j 個字元為 '*'，則字串 s 的第 i 個字元可以匹配字串 p 的第 j 個字元且接下來可以考慮匹配字串 s 的第 i+1 個字元和字串 p 的第 j 個字元或第 j+1 個字元，也可以考慮匹配字串 s 的第 i 個字元和字串 p 的第 j+1 個字元。
把上面這段寫成遞迴後，可以發現有許多重複的地方，例如遞迴順序為 (i, j) = (0, 0), (0, 1), (1, 1) 與 (i, j) = (0, 0), (1, 0), (1, 1)，在前者已經將 (1, 1) 答案算過、後者卻要重新計算 (1, 1)，聽起來就很 DP 對吧？所以這題其實在考 DP 啦XD
記得考慮空字串的情況：s = "", p = "*"，leetcode 蠻多字串題都要 handle 空字串的。

Code(C++)

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

心得

這題就是麻煩一點的 DP，不過我記得有一題 regular expression 的好像跟他一模一樣，也可能我記錯了。如果你寫的時候沒辦法直覺發現他是字串 DP，建議多練幾題類似的題目，例如字串編輯距離、最長共同子字串 … 等。

基本上字串 DP 的起手式就是：

type solve(string &a, string &b, int i, int j) {
    // ...
}

或是

for(int i=0; i<=n; i++) {
    for(int j=1; j<=m; j++) {
        // …
    }
}

要注意遞迴解的話，字串 a b 要用 reference，不然有時候會吃 TLE (copy string 坐遞迴的關係)。