# Python O(m*n) space and O(2*n) space

• ``````class Solution(object):
# O(m*n) space
def isMatch1(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
m,n = len(s), len(p)
dp = [[True]+[False]*m for _ in range (n+1)]
for i in range (1, n+1):
if p[i-1] == "*":
if i ==1: dp[i][0] = True
else: dp[i][0] = dp[i-2][0] or False
else:
dp[i][0] = False
for j in range (1, m+1):
if p[i-1] != "*":
dp[i][j] = dp[i-1][j-1] and (p[i-1] == s[j-1] or p[i-1] == ".")
else:
if i == 1: dp[i][j] = False
else: dp[i][j] = dp[i-2][j] or dp[i-1][j] or (dp[i][j-1] and (s[j-1] == p[i-2] or p[i-2] == "."))
return dp[-1][-1]

# O(2*n) space
def isMatch(self, s, p):
m, n = len(s), len(p)
dp = [[]]
dp.append([True]+[False]*m)
for i in range (1, (n+1)):
cur = []
if p[i-1] == "*":
if i==1:cur.append(True)
else:cur.append(dp[0][0])
else:
cur.append(False)
for j in range (1, m+1):
if p[i-1] != "*":
cur.append(dp[1][j-1] and (p[i-1] == s[j-1] or p[i-1] == "."))
else:
if i==1:
cur.append(False)
else:
cur.append(dp[0][j] or dp[1][j] or (cur[j-1] and (s[j-1] == p[i-2] or p[i-2] == ".")))
dp.pop(0)
dp.append(cur)
return dp[-1][-1]``````

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