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)

最后更新于