Day 49 of LeetCode

Documenting LeetCode solving.

Q126

10. Regular Expression Matching

Hard. DP

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = {}

        def dfs(i, j):
            if (i, j) in dp:
                return dp[(i, j)]
            if i >= len(s) and j >= len(p):
                return True
            if j >= len(p):
                return False

            match = i < len(s) and (s[i] == p[j] or p[j] == ".")
            # if there's *
            if (j + 1) < len(p) and p[j + 1] == "*":
                dp[(i, j)] = (dfs(i, j + 2) or              # don't use *
                              (match and dfs(i + 1, j)))    # use *
                return dp[(i, j)]
            # no *
            if match:
                dp[(i, j)] = dfs(i + 1, j + 1)
                return dp[(i, j)]
            # doesn't match
            dp[(i, j)] = False
            return False

        return dfs(0, 0)

Basically finished all new questions, start to review.