# Recursive solution in Python, with memoization

• ``````def isMatchHelper(self, s, p, prev,cache):
key = s+":"+p
if key in cache:
return cache[key]
#base case: both are empty:
if len(s) == 0 and len(p) == 0:
return True

#base case: if p is empty and s isn't:
if len(p) == 0:
return False

result = False

#character match:
if len(s) >= 1 and (s[0] == p[0] or p[0] == '.'):
if len(p) > 1 and p[1] == '*':
result = self.isMatchHelper(s[1:], p[1:], p[0],cache) or self.isMatchHelper(s, p[2:], "",cache)
else:
result = self.isMatchHelper(s[1:], p[1:], p[0],cache)
cache[key] = result
return result

#characters don't match

if p[0] != '*':
if len(p) == 1 or p[1] != '*':
return False
result = self.isMatchHelper(s, p[2:], "",cache)
cache[key]  = result
return result

if p[0] == '*':
if len(s) >=1 and (prev == s[0] or prev == '.'):
result = (self.isMatchHelper(s[1:], p[1:], "",cache) or self.isMatchHelper(s[1:], p, prev, cache) or self.isMatchHelper(s, p[1:], "" ,cache))
else:
result =  (self.isMatchHelper(s, p[1:], "" ,cache))

cache[key] = result
return result

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
'''
go character by character: a couple of situations:
i: character matches (either same char or .): trim one character from each and go on, or trim 2 characters from p and go on
ii: characer does not match but isnt *: check if next char is *, if so, trim 2 from p and go on
iii: character has *: check if prev character of p matches current char of s: if so, do as part i and ii. If not, trim one characer from p.

'''
cache = {}
return self.isMatchHelper(s, p, "", cache)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.