題目鏈接
tag:

• Hard

question：
??Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).
  The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = ""
Output: true
Explanation: '' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "ab"
Output: true
Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

思路：
??對于這種玩字符串的題目，動態(tài)規(guī)劃Dynamic Programming是一大神器痕寓，因為字符串跟其子串之間的關系十分密切，正好適合DP這種靠推導狀態(tài)轉移方程的特性又厉。那么先來定義dp數(shù)組吧硅急，我們使用一個二維dp數(shù)組圣猎，其中 dp[i][j] 表示 s中前i個字符組成的子串和p中前j個字符組成的子串是否能匹配。大小初始化為 (m+1) x (n+1)泻仙，加1的原因是要包含dp[0][0] 的情況，因為若s和p都為空的話量没，也應該返回true玉转，所以也要初始化 dp[0][0] 為true。還需要提前處理的一種情況是殴蹄，當s為空究抓，p為連續(xù)的星號時的情況猾担。由于星號是可以代表空串的，所以只要s為空刺下，那么連續(xù)的星號的位置都應該為true绑嘹，所以我們現(xiàn)將連續(xù)星號的位置都賦為true。然后就是推導一般的狀態(tài)轉移方程了橘茉，如何更新 dp[i][j]工腋，首先處理比較tricky的情況，若p中第j個字符是星號畅卓，由于星號可以匹配空串擅腰，所以如果p中的前j-1個字符跟s中前i個字符匹配成功了（dp[i][j-1] 為true）的話，那么 dp[i][j] 也能為true翁潘〕酶裕或者若 p中的前j個字符跟s中的前i-1個字符匹配成功了（dp[i-1][j] 為true）的話，那么 dp[i][j] 也能為true（因為星號可以匹配任意字符串拜马，再多加一個任意字符也沒問題）渗勘。若p中的第j個字符不是星號，對于一般情況俩莽，我們假設已經知道了s中前i-1個字符和p中前j-1個字符的匹配情況（即 dp[i-1][j-1] ）呀邢，那么現(xiàn)在只需要匹配s中的第i個字符跟p中的第j個字符，若二者相等（s[i-1] == p[j-1]）豹绪，或者p中的第j個字符是問號（p[j-1] == '?'）价淌，再與上 dp[i-1][j-1] 的值，就可以更新 dp[i][j] 了瞒津，參見代碼如下：

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