class Solution:
def isMatch(self, s: str, p: str) -> bool:
"""tc O(SP) sc P(SP)
dp[i][j]: s[:i] == p[:j]
corner case: if p == "", its up to if s is empty
case 0: s = "" : it's up to how the p is organized==> a*x*b* will match empty string
case 1: s[i-1] == p[j-1] -> dp[i][j] = dp[i-1][j-1]
case 2: p[j-1] == '.' -> dp[i][j] = dp[i-1][j-1]
case 3: p[j-1] == '*'
case 3.1 p[j-1] acts as empty "" -> dp[i][j] = dp[i][j-2]
case 3.2 s[i-1] == p[j-2] or p[j-2] = "." && dp[i][j-2] == True
"""
#corner case: p = ""
if len(p) == 0:
return len(s) == 0
dp = [ [False] *(n+1) for _ in range(m+1)]
# p != "" ========================>
dp[0][0] = True
#special case for example 4 to mach [empty string] t = "" == > p = #*#*#*#* ,
for j in range(2,n+1,2):
if p[j-1] == "*" :
dp[0][j] = dp[0][j-2]
for i in range(1,len(s)+1):
for j in range(1,len(p)+1):
if s[i-1] == p[j-1] or p[j-1] =="." :
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == "*":
if p[j-2] !='.' and s[i-1] != p[j-2]: # p[i-2:i] == ""
dp[i][j] = dp[i][j-2]
else: # p[i-2:i] == "" or s[i-1] or s[i-x:i-2]
dp[i][j] = dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j]
return dp[m][n]