Range DP

Range DP problems are problems that can use dp[i][j] to represent the states where i and j are the range in a list or array.

10. Regular Expression Matching

# Time complexity O(n) and the worst case is O(n^2)
# space complexity O(n^2)
from functools import lru_cache
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @lru_cache(None)
        def dp(i,j):
            if j==len(p):return i==len(s)
            firstmatch = len(s)>i and (p[j] in [s[i], '.'])
            if j<=len(p)-2 and p[j+1]=='*':
                #case 1 zero match
                case1 = dp(i, j+2)
                # case 2 many match
                case2 = firstmatch and dp(i+1, j)
                return case1 or case2
            return firstmatch and dp(i+1, j+1)
        return dp(0, 0)