2026-01-07 12:50:50 +0300 MSK

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        length1, length2 = len(s), len(p)
        cache = {}
        def search(i: int, j: int) -> bool:
            if (i, j) in cache:
                return cache[(i, j)]
            if i < length1:
                char = s[i]
            else:
                char = None
            if j < length2:
                pat = p[j]
            else:
                pat = None
            if char is None and pat is None:
                res = True
            elif char is None:
                res = pat == "*" and search(i, j + 1)
            elif pat is None:
                res = False
            elif pat == "?":
                res = search(i + 1, j + 1)
            elif pat == "*":
                nxt = j + 1
                while nxt < length2 and p[nxt] == "*":
                    nxt += 1
                res = search(i, nxt) or search(i + 1, nxt) or search(i + 1, j)
            else:
                res = pat == char and search(i + 1, j + 1)
            cache[(i, j)] = res
            return res

        return search(0, 0)