# Python DP solution in 36 ms

• draw a table and use different test cases.
After try and error, finally get AC.

``````def isMatch(self, s, p):
m = len(s)
n = len(p)
dp = [[True] + [False] * m]
for i in xrange(n):
dp.append([False]*(m+1))

for i in xrange(1, n + 1):
x = p[i-1]
if x == '*' and i > 1:
dp[i][0] = dp[i-2][0]
for j in xrange(1, m+1):
if x == '*':
dp[i][j] = dp[i-2][j] or dp[i-1][j] or (dp[i-1][j-1] and p[i-2] == s[j-1]) or (dp[i][j-1] and p[i-2]=='.')
elif x == '.' or x == s[j-1]:
dp[i][j] = dp[i-1][j-1]

return dp[n][m]``````

• @autekwing not sure how can you get 36ms when the first point in the runtime distribution graph is above 50ms...

Anyway, this is an 8-liner that I just wrote, hope you like it!

``````class Solution(object):
def isMatch(self, s, p, memo={("",""):True}):
if not p and s:      return False
if not s and p:      return set(p[1::2]) == {"*"} and not (len(p) % 2)
if (s,p) in memo:    return memo[s,p]

char, exp, prev = s[-1], p[-1], 0 if len(p) < 2 else p[-2]
memo[s,p] =\
(exp == '*' and ((prev in {char, '.'} and self.isMatch(s[:-1], p, memo)) or self.isMatch(s, p[:-2], memo)))\
or\
(exp in {char, '.'} and self.isMatch(s[:-1], p[:-1], memo))
return memo[s,p]

# 445 / 445 test cases passed.
# Status: Accepted
# Runtime: 72 ms
``````

• If you try: s="baaaa" p="ba*", you will get 'false' with your solution.

• @Coastchb It seems so.

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