Regular Expression Matching, leet code #12 in python.

[codewithsameerkhan-cc]

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
cache = {}

def helper(s, p):
if (s, p) in cache:
return cache[(s, p)]

if not p:
return not s

first_match = len(s) > 0 and (s[0] == p[0] or p[0] == '.')

if len(p) > 1 and p[1] == '*':
cache[(s, p)] = helper(s, p[2:]) or (first_match and helper(s[1:], p))
return cache[(s, p)]

if first_match:
cache[(s, p)] = helper(s[1:], p[1:])
return cache[(s, p)]

cache[(s, p)] = False
return False

return helper(s, p)