0044-wildcard-matching.py

"""
44. Wildcard Matching

Submitted: March 10, 2026

Runtime: 435 ms (beats 50.63%)
Memory: 157.00% (beats 5.00%)
"""

import functools

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        self.s = s
        # remove duplicates in p
        self.p = ""
        if "*" not in p:
            if "?" in p:
                return len(s) == len(p) and all(a == b for (a, b) in zip(s, p) if b != "?")
            else:
                return s == p
        if len(p) > 0:
            self.p += p[0]
            for c in p[1:]:
                if self.p[-1] == c == "*":
                    pass
                else:
                    self.p += c
        return self._isMatch(0, 0)

    @functools.cache
    def _isMatch(self, si, pi):
        s = self.s
        p = self.p
        n = len(s)
        m = len(p)
        if si == n and pi < m:
            # determine if the end is only "*" remaining
            return all(c == "*" for c in p[pi:])
        elif pi == m:
            return si == n
        c = s[si]
        d = p[pi]
        if d == "*":
            # try both moving forward and not moving forward on pi and si
            return (
                self._isMatch(si, pi + 1) or
                self._isMatch(si + 1, pi) or
                self._isMatch(si + 1, pi + 1)
            )
        elif d == "?" or d == c:
            # move forward
            return self._isMatch(si + 1, pi + 1)
        else:
            return False