0044 通配符匹配

from functools import lru_cache

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @lru_cache(maxsize=None)
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)

if __name__ == "__main__":
    sol = Solution()
    print(sol.isMatch("aa", "a"))      # False
    print(sol.isMatch("aa", "*"))      # True
    print(sol.isMatch("cb", "?a"))     # False
    print(sol.isMatch("adceb", "*a*b"))# True