题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wildcard-matching
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ’?’ 可以匹配任何单个字符。 ’*’ 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。 说明:
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”.

Case 1

输入:

s: 为空
p: 为空

输出:

true

演绎

Case 2

输入:

s: azc
p: ab?

输出:

false

演绎

Case 3

输入:

s: abc
p: ?b??

输出:

false

演绎

说明

如Case 1所示，base case当s和p均为空的情况下，匹配成功，记为1.
如Case 2,3所示，在没有*的情况下，s和q上的每一格应该是一一对应的关系，所以只需要沿着对角线一一匹配就可以了。
满足公式：s[i]==p[j] 或 s[i] == '?'时，表示前i个p和s成功匹配，
如Case 2所示，当前i个中出现不能匹配的情况，则后面就不需要匹配了，即当前i个字符出现不匹配的情况，前i+1个字符也必然不匹配，如若az不能与ab匹配，则azc也必然不能与ab?匹配。 所以当扫描到第i行第i列出现不匹配时，可以直接输出结果false。
如Case 3所示，当匹配到对角线的最后一格(Case 3图中加粗字体处的[c,?])，若仍有需要匹配的(即右方或下方还有空格)，表示匹配失败。若没有需要匹配的，表示匹配成功，返回true。

def isMatch(self, s: str, p: str) -> bool:
    table = []
    n_row = len(s) + 1
    n_column = len(p) + 1
    table = [[None] * n_column for _ in range(n_row)]
    table[0][0] = True
    for j in range(len(p)):
        table_j = j+1
        cur_p = p[j] #current p当前扫描到的通配符
        left_column = [e[table_j-1] for e in table]
        if cur_p == '*':
            # 找到左格为1的格子, 注意一下p[0]所在位置对应的是table[:][1]
            has_one = False
            for table_i,left in enumerate(left_column):
                if left == True:
                    # 从这一格开始往下全部置为1
                    for sub_i in range(table_i,n_row):
                        has_one = True
                        table[sub_i][table_j] = True
                    break
            if has_one == False: #左格没有为1的格子
                return False
        else:
            # 找到左上格为1的格子.如果没有则返回false
            has_one = False
            for start_i,left in enumerate(left_column):
                if left == True and start_i<n_row-1: #如果只有最后一行是1也不行
                    has_one = True
                    break
            if has_one == False:
                return False
            for table_i in range(start_i+1,n_row):
                if  table[table_i-1][table_j-1] == 1 and (cur_p == '?' or cur_p == s[table_i-1]):
                    table[table_i][table_j] = True
                else:
                    table[table_i][table_j] = False

    if table[-1][-1] == None: #p扫描完了，但是s还有多余。比如"ab"和"?"
        return False
    return table[-1][-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

另一个别人的代码，runtime要比我快，思路跟我的有些不一样：

​```python3
作者：powcai
链接：https://leetcode-cn.com/problems/two-sum/solution/shuang-zhi-zhen-he-dong-tai-gui-hua-by-powcai/
注释补充参考：
作者：*晴儿*
链接：https://blog.csdn.net/qq_34919415/article/details/86686508
class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        i = 0
        j = 0
        start = -1
        match = 0
        while i < len(s):
            # 非"*"的情况，一对一匹配,匹配成功一起往右下角移
            if j < len(p) and (s[i] == p[j] or p[j] == "?"):
                i += 1
                j += 1
            # 是"*"，记录i,j的位置。因为*能匹配空串，所以i不需要加1.
            elif j < len(p) and p[j] == "*":
                start = j
                match = i
                j += 1
            # p[j] 不是*，且前面有*，且不能匹配
            # 那么有可能是*未匹配完，
            # 所以回到最开始i的位置(这个回溯是这个思路的精髓所在)，j要指向p的后一个字母开始尝试匹配
            elif start != -1:
                j = start + 1
                match += 1
                i = match
            else:
                return False
         # s匹配完了，将多余的 * 直接匹配空串
        return all(x == "*" for x in p[j:])