O(m*n) time, O(n) space:

```
class Solution(object):
def isMatch(self, s, p):
m, n = len(s), len(p)
dp = [True] + [False] * n
for j in xrange(1, n+1):
dp[j] = p[j-1] == '*' and (j == 1 or dp[j-2])
for i in xrange(1, m+1):
pre, dp[0] = dp[0], False
for j in xrange(1, n+1):
tmp = dp[j]
if p[j-1] != '*':
dp[j] = pre and p[j-1] in [s[i-1], '.']
else:
dp[j] = dp[j-1] or j > 1 and (dp[j-2] or (dp[j] and p[j-2] in [s[i-1], '.']))
pre = tmp
return dp[-1]
```