10. Regular Expression Matching

'''
If length of p reaches end we should check whether we reached len(s) and return T or F
But if lenght of s reach end then we shouldnt check whether we reached len(p) instead we need to wait.
For e.g. s="a" p="aa*"

So three cases occur here.
1.If i has reached end
    |
    ---------->check j+2 is * or not. match zero characters of i fn(i,j+2)
2.If i has not reached but you found matching
    |
    ---------->check if j+2 is *
        |
        -------> do zero or more occurences match fn(i+1,j) or fn(i,j+20
    ---------->match single character since its matching


3.You didnt find matching
    |
    ---------->check j+2 is * or not .match zero characters of i fn(i,j+2)
'''

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i,j):
            ans=False
            if j>=len(p):
                return i>=len(s)

            if i==len(s):
                if j+1<len(p) and p[j+1]=='*':
                    ans = ans or dfs(i,j+2)


            elif s[i]==p[j] or p[j]=='.':
                if j+1<len(p) and p[j+1]=='*':
                    ans = ans or dfs(i+1,j)
                    ans = ans or dfs(i,j+2)

                ans = ans or dfs(i+1,j+1)

            else:
                if j+1<len(p) and p[j+1]=='*':
                    ans = ans or dfs(i,j+2)

            return ans
        return dfs(0,0)
#2.Concise version

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m,n=len(s),len(p)
        @lru_cache()
        def dfs(i,j):
            if i>=m and j>=n:
                return True
            if j>=n:return False

            match= (i<m) and (s[i]==p[j] or (p[j]=='.'))

            if j+1<n and p[j+1]=='*':
                return (dfs(i,j+2) or (match and dfs(i+1,j)))
            if match:
                return dfs(i+1,j+1)
            return False
        return dfs(0,0)