# Recursive Python Solution with Cache (Memoization)

• I found this method simpler to understand than the dynamic programming solutions using a two dimensional table.

This method differs in that before a recursive call to isMatch, the algorithm checks to see if the next state already exists in the cache / dictionary and uses that precomputed value instead. If the next state is not in the dictionary, it computes it recursively and stores the result in the cache for the future.

In terms of code quality and variable names, there could be some improvement, but I felt the algorithm is easier to understand.

Here is the code:

class Solution(object):

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
return self.isMatchHelper(s, p, {})

def isMatchHelper(self, s, p, cache):
# if at the end of the pattern, we must also be at the end of the text
if not p:
return not s

curr_match = bool(s) and p[0] in {s[0], '.'}

if len(p) >= 2 and p[1] == '*':
skip = False
if (s, p[2:]) in cache:
skip = cache[(s, p[2:])]
else:
skip = self.isMatchHelper(s, p[2:], cache)
cache[(s, p[2:])] = skip

if curr_match:
if (s[1:], p) in cache:
delete = cache[(s[1:], p)]
else:
delete = self.isMatchHelper(s[1:], p, cache)
cache[(s[1:], p)] = delete

return skip or (curr_match and delete)

else:
if curr_match:
if (s[1:], p[1:]) in cache:
general = cache[(s[1:], p[1:])]
else:
general = self.isMatchHelper(s[1:], p[1:], cache)
cache[(s[1:], p[1:])] = general

return curr_match and general

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