Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.


'.' Matches any single character.
'*' Matches zero or more of the preceding element.


The matching should cover the entire input string (not partial).

Note:


       s could be empty and contains only lowercase letters a-z.
       p could be empty and contains only lowercase letters a-z, and characters like . or *.


Example 1:


Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:


Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".


Example 3:


Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


Example 4:


Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".


Example 5:


Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     cache = {}
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
 
         if (s, p) in self.cache:
             return self.cache[(s, p)]
         if not p:
             return not s
         if p[-1] == '*':
             if self.isMatch(s, p[:-2]):
                 self.cache[(s, p)] = True
                 return True
             if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
                 self.cache[(s, p)] = True
                 return True
         if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
             self.cache[(s, p)] = True
             return True
         self.cache[(s, p)] = False
         return False

class Solution(object):
     def isMatch(self, string, expr):
         self.memo = {(0,0):True}
         self.string = string
         self.expr = expr
         N = len(string)
         M = len(expr)
 
         return self.get(N, M)
 
     def get(self, i, j):
         if i < 0 or j < 0:
             return False
 
         if (i,j) not in self.memo:
             self.memo[(i,j)] = self.eval(i,j)
 
         return self.memo[(i,j)]
 
     def eval(self, i, j):
         if j <= 0: return False
         if self.expr[j-1] == '*':
             prev_char = self.expr[j-2]
             
             if prev_char == '.' or i >= 1 and prev_char == self.string[i-1]:
                 if self.get(i-1, j):
                     return True
                 
             return self.get(i, j-2)
         
         else:
             if self.expr[j-1] == '.' or i >= 1 and self.expr[j-1] == self.string[i-1]:
                 return self.get(i-1, j-1)
             
             return False


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         
         self.mem = {}
         self.t = s
         self.p = p
         
         return self.match(0,0)
     
     def match(self, i, j):
         
         if (i,j) not in self.mem:
             if j == len(self.p):
                 res = i == len(self.t)
                 
             else:
                 if j+1 < len(self.p) and self.p[j+1] == '*':
                     res = self.match(i, j+2) or (i < len(self.t) and self.p[j] in {self.t[i], '.'} and self.match(i+1, j))
                 else:
                     res = i < len(self.t) and self.p[j] in {self.t[i], '.'} and self.match(i+1, j+1)
                     
             self.mem[i, j] = res
                 
         return self.mem[i, j]
         


class Solution:
     def __init__(self):
         self.dp = {}
 
     def isMatch(self, text, pattern):
         if not pattern:
             return not text
         
         if (text, pattern) in self.dp:
             return self.dp[(text, pattern)]
 
         first_match = bool(text) and pattern[0] in {text[0], '.'}
 
         if len(pattern) >= 2 and pattern[1] == '*':
             
             self.dp[(text, pattern)] = self.isMatch(text, pattern[2:]) or \
                                        first_match and self.isMatch(text[1:], pattern)
         else:
             self.dp[(text, pattern)] = first_match and self.isMatch(text[1:], pattern[1:])
         
         return self.dp[(text, pattern)]

class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         def parsePatern(p):
             pi=len(p)-1
             while pi>=0:
                 if p[pi]=='*':                    
                     if pi==0: raise Exception('Invalid pattern!')
                     yield (p[pi-1], 1)
                     pi-=2
                 else:
                     yield (p[pi], 0)
                     pi-=1
                     
         from collections import deque
         # p = b*bab*a*
         # s = bbbba
         if not p: return p==s
         plist = list(parsePatern(p)) # [('a', 1), ('b', 1), ('a', 0), ('b', 0), ('b', 1)]         
         P = len(plist)
         #q = deque([(0, len(s)-1)])
         q = set([(0, len(s)-1)])
         seen = set()
         """
         q = [ (('a',1), 4) ]
         q = [ (('b',1), 4), (('b',1), 3) ] 
         q = [ (('a', 0), 4), (('a',0), 3)), (('a',0), 2), (('a',0), 1), (('a',0), 0), (('a',0), -1)]
         q = [ (('b', 0), 3) ]
         q = [ (('b', 1), 2)]
         q = [ (('', 0), 2), (('', 0), 1), (('', 0), 0), (('', 0), -1)]
         (('', 0), -1)-> true
         
         """
         while q:
             #print(q)
             pat_i, si = q.pop()  
             if (pat_i, si) in seen: 
                 #print('seen')
                 continue
             
             seen.add((pat_i, si))
             pat, is_as = plist[pat_i] if pat_i<P else ('', 0)
             """
             1. a, 1
                 1: bbbb
                 0: bbbba
             2. b, 1
                 10: bbbb
                 11: bbb
                 12: bb
                 13: b
                 14: ''
                 00: bbbba
             3. a, 0
                 001: bbbb
             4. b, 0
                 0011: bbb
             5, b, 1:
                 00110: bbb
                 00111: bb
                 00112: b
                 00113: ''
             6, '', 0
                 00113 -> true
             """
             if not pat and si<0: return True                                    
             if is_as:
                 # match 0 -> n
                 q.add((pat_i+1, si))
                 #q.append((pat_i+1, si))
                 #if (pat_i+1, si) in q: print('dup', (pat_i+1, si))
                 while si>=0 and (s[si]==pat or pat=='.'):
                     si-=1
                     #if (pat_i+1, si) in q: print('dup', (pat_i+1, si))
                     q.add((pat_i+1, si))
                     #q.append((pat_i+1, si))
             elif si>=0 and (s[si]==pat or pat=='.'):
                 #if (pat_i+1, si-1) in q: print('dup', (pat_i+1, si))
                 q.add((pat_i+1, si-1))
                 #q.append((pat_i+1, si-1))
             
         return False


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         if not p and len(s) != 0:
             return False
         memo = {}
         def dp(i, j):
             if (i,j) not in memo:
                 if j == len(p):
                     res = i == len(s)
                 else:
                     # head must in s and p[j] should be s[i] or '.' 
                     head_match = i < len(s) and p[j] in {s[i] ,'.'}
                     # check
                     if j+1 < len(p) and p[j+1] == '*':
                         res = dp(i, j+2) or head_match and dp(i+1, j) 
                     else:
                         res = head_match and dp(i+1,j+1)
                 memo[(i,j)] = res
             return memo[(i,j)]
         
         return dp(0,0)

class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         self.maps = dict()
         return self.dfs(s, p)
         
     def dfs(self, s, p):
         key = (s, p)
         if key in self.maps:
             return self.maps[key]
 
         if not s and not p:
             return True
         
         if s and not p:
             return False
 
         if len(p) > 1 and p[1] == '*':
             if (s and s[0] == p[0]) or (p[0] == '.' and s):
                 self.maps[key] = self.dfs(s[1:], p[2:]) or self.dfs(s[1:], p) or  self.dfs(s, p[2:])
             else:
                 self.maps[key] = self.dfs(s, p[2:])
         elif (s and s[0] == p[0]) or (p[0] == '.' and s):
             self.maps[key] = self.dfs(s[1:], p[1:])
         return self.maps[key] if key in self.maps else False

class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         m, n = len(s), len(p)
         dp=[[False]*(n+1) for _ in range(m+1)]
         dp[0][0]=True
         for j in range(2, n+1):
             if p[j-1]=="*":
                 dp[0][j]=dp[0][j-2]
         for i in range(1, m+1):
             for j in range(1,n+1):
                 if p[j-1]=="*":
                     if p[j-2]==s[i-1] or p[j-2]=='.':
                         dp[i][j]= dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
                     elif p[j-2]!=s[i-1]:
                         dp[i][j]=dp[i][j-2]
                 elif p[j-1]==s[i-1] or p[j-1]=='.':
                     dp[i][j]=dp[i-1][j-1]
         return dp[m][n]


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         m = {}
         def dp(i, j):
             print((i,j))
             if (i, j) not in m:
                 if j == len(p):
                     ans = i == len(s)
                 else:
                     first_match = i < len(s) and p[j] in {s[i], '.'}
                     if j+1 < len(p) and p[j+1] == '*':
                         ans = dp(i, j+2) or first_match and dp(i+1, j)
                     else:
                         ans = first_match and dp(i+1, j+1)
 
                 m[i, j] = ans
             return m[i, j]
 
         return dp(0, 0)


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
         dp[-1][-1] = True
         
         for i in range(len(s), -1, -1):
             for j in range(len(p) - 1, -1, -1):
                 first_match = i < len(s) and p[j] in {s[i], '.'}
                 if j + 1 < len(p) and p[j+1] is '*':
                     dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                 else:
                     dp[i][j] = first_match and dp[i+1][j+1]
                     
         return dp[0][0]
                     
                         
                     
                     
                     
                 


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         memo = {}
         def dp(i, j):
             print((i,j))
             if (i, j) not in memo:
                 if j == len(p):
                     ans = i == len(s)
                 else:
                     first_match = i < len(s) and p[j] in {s[i], '.'}
                     if j+1 < len(p) and p[j+1] == '*':
                         ans = dp(i, j+2) or first_match and dp(i+1, j)
                     else:
                         ans = first_match and dp(i+1, j+1)
 
                 memo[i, j] = ans
             return memo[i, j]
 
         return dp(0, 0)


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         import re
         pattern = re.compile(p)
         match = pattern.match(s)
         if match:
             try:
                 return match.group() == s
             except:
                 return False
             finally:
                 pass
         else:
             return False