44.-tong-pei-fu-pi-pei.md

44. 通配符匹配

https://leetcode-cn.com/problems/wildcard-matching/

解法一：直接法

难点还是在于*的处理_。_i，j分别指向字符串和模式串

模式串遇到*号时，记录星号位置star，以及i位置match，然后i不动，j跳过星号，进入下一轮比对，直到星号后的字符与i匹配上为止。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        i, j = 0, 0
        star, match = -1, -1
        while i < len(s):
            #若恰好适配
            if j < len(p) and (s[i] == p[j] or p[j] == '?'):  
                i += 1    #i，j都往前一步
                j += 1
            #若模式串遇到*号
            elif j < len(p) and p[j] == '*':  
                star = j  #记录*位置，以供回退
                match = i  #记录i位置
                j += 1    #j往前，i不动
            #若*号后的字符还没被匹配，则*号再匹配s串的一位，继续回滚
            elif star != -1:  
                j = star + 1  #模式串回滚到*号后一位
                match += 1    #*号再匹配s一位
                i = match                
            else:
                return False

        while j < len(p) and p[j] == '*':  #若p还有剩余，检查是不是*
            j += 1
        return j == len(p)