# 10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

###### Hard

##### Solution(Recursion)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        if p == "":
            return s == ""
        
        first = s != "" and (p[0] == s[0] or p[0] == ".")

        if len(p) >= 2 and p[1] == "*":
            return self.isMatch(s,p[2:]) or (first and self.isMatch(s[1:],p))
        else:
            return first and self.isMatch(s[1:],p[1:])

> Runtime: 1132 ms, faster than 24.10% of Python3 online submissions for Regular Expression Matching.
> Memory Usage: 14.3 MB, less than 59.97% of Python3 online submissions for Regular Expression Matching.

##### Solution(DP Top-Down)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        catch = {}

        def dfs(i,j):
            if (i,j) in catch:
                return catch[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 j+1 < len(p) and p[j+1] == "*":
                ans = dfs(i,j+2) or (match and dfs(i+1,j))
            else:
                ans = match and dfs(i+1,j+1)

            catch[i,j] = ans
            
            return catch[i,j]

        return dfs(0,0)

> Runtime: 36 ms, faster than 96.27% of Python3 online submissions for Regular Expression Matching.
> Memory Usage: 14.4 MB, less than 59.97% of Python3 online submissions for Regular Expression Matching.