leetcode-44通配符比對

給定一個字元串 (s) 和一個字元模式 § ，實作一個支援 ‘?’ 和 ‘*’ 的通配符比對。

‘?’ 可以比對任何單個字元。

‘*’ 可以比對任意字元串（包括空字元串）。

兩個字元串完全比對才算比對成功。

說明:

s 可能為空，且隻包含從 a-z 的小寫字母。

p 可能為空，且隻包含從 a-z 的小寫字母，以及字元 ? 和 *。

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法比對 "aa" 整個字元串。
示例 2:

輸入:
s = "aa"
p = "*"
輸出: true
解釋: '*' 可以比對任意字元串。
示例 3:

輸入:
s = "cb"
p = "?a"
輸出: false
解釋: '?' 可以比對 'c', 但第二個 'a' 無法比對 'b'。
示例 4:

輸入:
s = "adceb"
p = "*a*b"
輸出: true
解釋: 第一個 '*' 可以比對空字元串, 第二個 '*' 可以比對字元串 "dce".
示例 5:

輸入:
s = "acdcb"
p = "a*c?b"
輸出: false
           

題解

f[i][j]代表s[1:i],p[1:j]是否比對，如果p[j] == '?'或者p[j] == s[i]的話，那麼p[j]一定要比對字母，如果p[j] 是一個字母且p[j] != s[i]那麼比對失敗，如果p[j] == '*'的話那麼可以選擇比對一個字元或者不比對。

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(),m = p.size();
        vector<vector<int> >f(n + 1,vector<int>(m + 1));
        f[0][0] = true;
        for(int i = 1;i <= m;i ++){
            if(p[i - 1] == '*')f[0][i] = f[0][i - 1];
        }
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?')f[i][j] = f[i - 1][j - 1];
                else if(p[j - 1] != '*')f[i][j] = false;
                else{
                    f[i][j] = f[i - 1][j] | f[i][j - 1];
                }
            }
        }

        return f[n][m];
    }
};