解法一：動態(tài)規(guī)劃

由于此題中"*"可以匹配多個字符（包括空字符），因此枚舉所有可能性較為麻煩，一種簡單的思路是采用動態(tài)規(guī)劃算法進行求解，具體思路如下：

定義動態(tài)規(guī)劃數(shù)組dp，其中dp[i] [j]表示「s字符串的前i個字符與p字符串的前j個字符是否匹配」。而對于每個位置，有如下三種情況：

1. 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]不能匹配；
2. 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個字符也能匹配，即：“*”匹配單個字符；
3. p字符串第j個位置為一個字母，且與s字符串第i個位置相同：顯而易見dp[i] [j] = dp[i - 1] [j - 1]。

根據(jù)上述思路，可以得到代碼如下：

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數(shù)組
        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]; 
    }
};

該方法需要兩層循環(huán)來更新dp數(shù)組，因此時間復雜度為O(MN)；該方法需要定義二維數(shù)組dp，因此空間復雜度為O(MN)，其中：M和N分別為兩個字符串的長度。

解法二：雙指針

解法一定義了dp數(shù)組來進行遞推，然而，可以進一步優(yōu)化空間復雜度。

解法二采用「雙指針」算法，定義兩個指針i，j，分別對s字符串和p字符串進行遍歷。此外，解法二定義指針match和star，分別表示「未匹配的位置」以及「"*"號所在的位置」，當遇到p字符串當前字符為星號時更新match = i。

1. 當s[i]與p[j]相同、或p[j]為"?"時，即：當前字符串是「單字符匹配的情況」，i指針與j指針向前遍歷即可；
2. 當p字符串遇到"*"時，更新star，讓其指向該位置，j向前；
3. 當不符合前面兩種情況時，即s字符串和p字符串當前字符都是「小寫字母」且不相等時，此時分兩種情況：
   1. star取值為-1，說明之前沒有出現(xiàn)"*"，此時直接返回false；
   2. star取值不為-1，說明之前出現(xiàn)過"*"，則將j指針更新到star+1的位置，i指針更新到match的下一個位置，重新開始匹配。具體過程如圖所示。
4. 在遍歷完s字符串后，若p字符串仍未遍歷完，則繼續(xù)遍歷p，且「必須全部為"*"」才可以（匹配空字符），否則匹配失敗。

基于上述思路，實現(xiàn)代碼如下：

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位于第一個位置），后續(xù)每次遇到b字符，都需要重新從第二個位置開始遍歷p字符串，因此最壞時間復雜度為O(MN)。

此方法不需要額外存儲空間，空間復雜度為O(1)。