# Python solution with detailed explanation

• Solution

Regular Expression Matching https://leetcode.com/problems/regular-expression-matching/

Algorithm

• Similar idea like https://leetcode.com/problems/wildcard-matching/, except we need to proactively scan the next character and if it " * ", then take we can either accept or reject.
• Tricky boundary condition is "", "a*" or "", ".*c*". We need to check: i == len(s) and p[j:].count('*')*2 == len(p[j:])
``````from collections import defaultdict
class Solution(object):
def helper(self, i, j, s, p, cache):
if i == len(s) and j == len(p):
return True
elif i == len(s) and p[j:].count('*')*2 == len(p[j:]):
return True
elif i == len(s) or j == len(p):
return False
elif i in cache and j in cache[i]:
return cache[i][j]
else:
if j+1 != len(p) and p[j+1] == "*" and p[j] != ".":
x1 = ((s[i] == p[j]) and self.helper(i+1, j, s, p, cache))
cache[i][j] = x1 or self.helper(i, j+2, s, p, cache)
elif j+1 != len(p) and p[j+1] == "*" and p[j] == ".":
cache[i][j] = self.helper(i, j+2, s, p, cache) or self.helper(i+1, j, s, p, cache)
elif p[j] == "." or s[i] == p[j]:
cache[i][j] = self.helper(i+1, j+1, s, p, cache)
else:
cache[i][j] = False
return cache[i][j]

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
return self.helper(0, 0, s, p, defaultdict(dict))
``````

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