通配符匹配

通配符匹配_牛客题霸_牛客网

问题简述

请实现支持'?'and'*'.的通配符模式匹配
'?' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。

详细用例见链接

思路：动态规划

• 定义 dp(i, j) 表示 s[:i] 与 p[:j] 能否匹配；

• 分情况讨论：

  • i==0, j==0 时，匹配；

  • i==0, j!=0 时，只能当 p[:j] 全为 * 时才能匹配；

  • i!=0, j==0 时，始终不匹配；

  • s[i - 1] == p[j - 1] or p[j - 1] == '?' 时，需要 dp(i-1,j-1) 匹配；

  • p[j - 1] == '*' 时，需要 dp(i-1,j) 或 dp(i,j-1) 匹配；

  • 其他情况，不匹配

递归写法

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(i, j):
            # 空串与空串
            if i == 0 and j == 0: return True
            # p 为空，s 不为空使，始终不匹配
            if j == 0: return False
            # s 为空时，只有 p 的前 j 个字符都是 '*' 才能匹配成功（这是最容易弄错的地方）
            if i == 0: return p[:j] == '*' * j  # p[j - 1] == '*' and dp(i, j - 1)

            # '?' 能匹配任意字符（不能匹配空字符）
            if s[i - 1] == p[j - 1] or p[j - 1] == '?':
                return dp(i - 1, j - 1)
            # 如果当前 p[j - 1] 是 '*'，那么有两种可能匹配成功：
            #   1) s[:i - 1] 和 p[:j]，此时 '*' 匹配的是 空字符
            #   2) s[:i] 和 p[:j - 1]，此时 '*' 匹配的是 s[i - 1]
            elif p[j - 1] == '*':
                return dp(i - 1, j) or dp(i, j - 1)
            else:
                return False
        
        return dp(len(s), len(p))

迭代写法（略）