Regular Expression Matching

'''
Check for wildcard string matching,Both problem is similar
Question:
'.' can match with any character
'a*' can match with '','a','aa','aaa','aaaa' can product infinite k
'''
def fun(s,p,i,j,dp):
    if i<0 and j<0:
        return True

    if j<0:
        return False

    if i<0:
        while j>=0 and p[j]=='*':
            j-=2
        return j<0

    if dp[i][j]!=-1:
        return dp[i][j]

    ans=False
    if s[i]==p[j] or p[j]=='.':
        ans=fun(s,p,i-1,j-1,dp)

    elif p[j]=='*':
        ans=fun(s,p,i,j-2,dp) #case1: we can skip the previous character of * completely, it consumed the previous char and make that ''
        if j>0 and (s[i]==p[j-1] or p[j-1]=='.'): #we can check if prev char is matching the current str[i], so you can consider * will match the ith char and now you can check for other chars of str. Here we are not reducing the pattern because * can product infinite prev_char so may be s[i-1] can also be same as the prev char of *
            ans=ans or fun(s,p,i-1,j,dp)

    dp[i][j]=ans
    return ans

class Solution:
    def isMatch(self,s,p):
        dp=[[-1]*len(p) for _ in range(len(s))]
        return fun(s,p,len(s)-1,len(p)-1,dp)