class Solution():
def isMatch(self, s, p):
result = [[False for j in range(len(p) + 1)] for i in range(len(s) + 1)]
result[0][0] = True
for i in range(2, len(p) + 1):
if p[i-1] == '*':
result[0][i] = result[0][i-2]
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
if p[j-1] != '*':
result[i][j] = result[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
else:
result[i][j] = result[i][j-2] or (result[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
return result[len(s)][len(p)]
if __name__ == "__main__":
assert Solution().isMatch("abccd", "abc*d") == True
assert Solution().isMatch("abab", "a*b*") == False
assert Solution().isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*c") == False
assert Solution().isMatch("aa","a") == False
assert Solution().isMatch("aa","aa") == True
assert Solution().isMatch("aaa","aa") == False
assert Solution().isMatch("aa", "a*") == True
assert Solution().isMatch("aa", ".*") == True
assert Solution().isMatch("ab", ".*") == True
assert Solution().isMatch("aab", "c*a*b") == True