2026-01-07 13:23:17 +0300 MSK

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        length1, length2 = len(s), len(p)
        cache = {}

        def match(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 pat is None:
                res = False
            elif char is None:
                res = (length2 - j) % 2 == 0
                if res:
                    for cur_j in range(j, length2, 2):
                        if p[cur_j] == "*" or p[cur_j + 1] != "*":
                            res = False
                            break
            else:
                if j + 1 < length2:
                    pat_nxt = p[j + 1]
                else:
                    pat_nxt = None
                valid = pat == "." or char == pat
                if pat_nxt and pat_nxt == "*":
                    res = (valid and match(i + 1, j)) or match(i, j + 2)
                else:
                    res = valid and match(i + 1, j + 1)

            cache[(i, j)] = res
            return res

        return match(0, 0)