```
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
lenS, lenP = len(s), len(p)
# dp[i][j]==True means s[:i] matches p[:j]
dp = [[False]*(lenP+1) for i in xrange(lenS+1)]
dp[0][0] = True
for si in xrange(lenS+1): # starting from 0, which inits the dp[0][:]
for pi in xrange(1, lenP+1): # starting from 1
if p[pi-1] != '*':
dp[si][pi] = si>0 and dp[si-1][pi-1] and (s[si-1]==p[pi-1] or p[pi-1]=='.')
else: # handle '*'
# matches zero time or more than once
dp[si][pi] = dp[si][pi-2] or (si>0 and dp[si-1][pi] and (s[si-1]==p[pi-2] or p[pi-2]=='.'))
return dp[lenS][lenP]
```