leetcode上這個題目出現(xiàn)了兩次春畔，基本都是要求答題者寫代碼完成 '*' 和 '?' 通配符的匹配优俘。
一下摘錄其中一題：

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).
The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "") → true
isMatch("aa", "a") → true
isMatch("ab", "?") → true
isMatch("aab", "ca*b") → false

解決這道題可以用遞歸的方法坊罢，遞歸的思路代碼如下：
下列代碼中迈喉，首先判斷特殊情況（終止條件）, 分兩種情況討論

• 當(dāng)傳入的p為空時。
• 當(dāng)傳入的s為空時览爵。
  然后考慮一般情況跪呈，也分兩種情況討論：
• p 開頭為 '*'段磨，若開頭為星號，接下來有三種匹配方式：
  • p[0] 僅匹配單個字符 s[0]耗绿，p[1] ~ p[m] 匹配 s[1] ~ s[n]苹支，此時遞歸調(diào)用 isMatch(s.substr(1,s.size() - 1), p.substr(1,p.size() - 1))
  • p[0] 匹配字符串 s[0] ~ s[i]，此時遞歸調(diào)用isMatch(s.substr(1,s.size() - 1), p.substr(0,p.size() ))
  • p[0]匹配空字符串误阻，此時遞歸調(diào)用isMatch(s.substr(0,s.size() ), p.substr(1,p.size() - 1))
• p 開頭不為 '*'债蜜，如果p[0] 與 s[0]匹配，此時遞歸調(diào)用 isMatch(s.substr(1,s.size() - 1), p.substr(1,p.size() - 1))究反，否則匹配失敗寻定。
  將以上思路寫成代碼如下：

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.size() == 0) {
            if(s.size() == 0)
            return true;
            return false;
        }
        if(s.size() == 0) {
            if(p[0] == '*')
                return isMatch(s.substr(0,s.size()), p.substr(1,p.size() - 1));
            return false;
        }
        bool res;
        if(p[0] == '*') {
            res = isMatch(s.substr(1,s.size() - 1), p.substr(1,p.size() - 1)) || 
            isMatch(s.substr(1,s.size() - 1), p.substr(0,p.size())) || 
            isMatch(s.substr(0,s.size()), p.substr(1,p.size() - 1));
        }
        else {
            if(p[0] == s[0] || p[0] == '?')
                res = isMatch(s.substr(1,s.size() - 1), p.substr(1,p.size() - 1));
            else
                return false;
        }
        return res;
    }
};

但是，遞歸的思路解法速度不夠精耐，再leetcode上會超時狼速，那么就需要我們用動態(tài)規(guī)劃解決。
同樣的道理黍氮，根據(jù)上述遞歸的思路寫出遞推關(guān)系式

P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

依據(jù)上述關(guān)系唐含，可以寫出新的代碼，代碼如下：

class Solution {
public:
    bool isMatch(string s, string p) { 
        int m = s.length(), n = p.length();
        vector<bool> cur(m + 1, false); 
        cur[0] = true;
        for (int j = 1; j <= n; j++) {
            bool pre = cur[0]; // use the value before update
            cur[0] = cur[0] && p[j - 1] == '*'; 
            for (int i = 1; i <= m; i++) {
                bool temp = cur[i]; // record the value before update
                if (p[j - 1] != '*')
                    cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
                else cur[i] = cur[i - 1] || cur[i];
                pre = temp;
            }
        }
        return cur[m]; 
    }
};