leetcode problem 44

problem_44_wildcard_matching.py

"""This isn't the most efficient, but is the most "natural" to me.

match(i, j) => do letters `s[:i]` match chars `p[:j]`

- If i == -1, return False
- Set letter to the last of letters and char to last of chars
- If chars is empty, the only match is if letters is empty
- If char is *, did s[:i-1] match p[:j] or did s[:i] match p[:j-1]?
- Else does char match letter and did s[:i-1] match p[:j-1]?

"""

from functools import cache

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        @cache
        def match(i, j):
            if i == -1:
                return False

            letter = s[:i][-1] if i else ""
            char = p[:j][-1] if j else ""

            if char == "":
                return letter == ""
            if char == '*':
                return match(i - 1, j) or match(i, j - 1)
            return (char == letter or char == '?') and match(i - 1, j - 1)


        return match(len(s), len(p))