解法一：动态规划

由于此题中"*"可以匹配多个字符（包括空字符），因此枚举所有可能性较为麻烦，一种简单的思路是采用动态规划算法进行求解，具体思路如下：

定义动态规划数组dp，其中dp[i] [j]表示「s字符串的前i个字符与p字符串的前j个字符是否匹配」。而对于每个位置，有如下三种情况：

p字符串第j个位置为"?"时：由于"?"可以匹配任意单个字符，因此dp[i] [j]的匹配情况可以由dp[i-1] [j-1]递推得到：dp[i] [j] = dp[i - 1] [j - 1]；即：若在s字符串的前i个字符与p字符串的前j个字符成功匹配，则dp[i] [j]也能成功匹配；否则dp[i] [j]不能匹配；
p字符串第j个位置为"*"时：由于该字符可以匹配任意字符串，包括空字符，因此dp[i] [j]可以通过dp[i - 1] [j]以及dp[i] [j - 1]递推得到：
1. 若s字符串的前i-1个字符与p字符串的前j个字符匹配，则s字符串的前i个字符与p字符串的前j个字符也能匹配，即：“*”匹配空字符；
2. 若s字符串的前i个字符与p字符串的前j-1个字符匹配，则s字符串的前i个字符与p字符串的前j个字符也能匹配，即：“*”匹配单个字符；
p字符串第j个位置为一个字母，且与s字符串第i个位置相同：显而易见dp[i] [j] = dp[i - 1] [j - 1]。

根据上述思路，可以得到代码如下：

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p); 
        vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false)); // 定义dp数组
        dp[0][0] = true; // 初始化
        // 初始化
        for (int i = 1; i <= n; i ++) {
            if (p[i - 1] == '*') 
                dp[0][i] = true; 
            else
                break; 
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?') // 若当前位置s字符串与p字符串字符相同，或当前p字符串的字符为"?"
                    dp[i][j] = dp[i - 1][j - 1]; 
                if (p[j - 1] == '*') // 当前p字符串的字符为"*"
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; 
            }
        }
        return dp[m][n]; 
    }
};

该方法需要两层循环来更新dp数组，因此时间复杂度为O(MN)；该方法需要定义二维数组dp，因此空间复杂度为O(MN)，其中：M和N分别为两个字符串的长度。

解法二：双指针

解法一定义了dp数组来进行递推，然而，可以进一步优化空间复杂度。

解法二采用「双指针」算法，定义两个指针i，j，分别对s字符串和p字符串进行遍历。此外，解法二定义指针match和star，分别表示「未匹配的位置」以及「"*"号所在的位置」，当遇到p字符串当前字符为星号时更新match = i。

当s[i]与p[j]相同、或p[j]为"?"时，即：当前字符串是「单字符匹配的情况」，i指针与j指针向前遍历即可；
当p字符串遇到"*"时，更新star，让其指向该位置，j向前；
当不符合前面两种情况时，即s字符串和p字符串当前字符都是「小写字母」且不相等时，此时分两种情况：
1. star取值为-1，说明之前没有出现"*"，此时直接返回false；
2. star取值不为-1，说明之前出现过"*"，则将j指针更新到star+1的位置，i指针更新到match的下一个位置，重新开始匹配。具体过程如图所示。
在遍历完s字符串后，若p字符串仍未遍历完，则继续遍历p，且「必须全部为"*"」才可以（匹配空字符），否则匹配失败。

图片说明

基于上述思路，实现代码如下：

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p); 
        int i = 0, j = 0, star = -1; // i, j为遍历两个字符串的指针，star指向"*"字符
        int match = 0; // 记录上次未匹配的位置
        while (i < m) {
            if (s[i] == p[j] || p[j] == '?') { // 若当前位置s字符串与p字符串字符相同，或当前p字符串的字符为"?"
                i ++; 
                j ++; 
            } else if (p[j] == '*') { // 当前p字符串的字符为"*"
                star = j; 
                      match = i; // 更新match
                j ++; 
            } else {
                if (star >= 0) { // 前面的位置有"*"
                    j = star + 1; 
                    match ++; 
                    i = match; 
                }
                else // 未匹配成功，且之前没有"*"
                    return false; 
            }
        }
        while (j < n) { // p长度较长，则必须全为"*"
            if (p[j] != '*') 
                return false; 
            j ++; 
        }
        return true; 
    }
};

此方法的最坏时间复杂度为O(MN)，其中M、N分别为两个字符串的长度，解释如下：

当s字符串为"aaaaaa"，p字符串为"*aaab"时（star位于第一个位置），后续每次遇到b字符，都需要重新从第二个位置开始遍历p字符串，因此最坏时间复杂度为O(MN)。

此方法不需要额外存储空间，空间复杂度为O(1)。

题解 | #通配符匹配#

解法一：动态规划

解法二：双指针