1
class Solution:
2
    def isMatch(self, s, p):
3
        n = len(s)
4
        m = len(p)
5
        dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]
6
        dp[0][0] = True
7
        for c in range(1, m + 1):
8
            if p[c - 1] == "*" and c > 1:
9
                dp[0][c] = dp[0][c - 2]
10
        for r in range(1, n + 1):
11
            for c in range(1, m + 1):
12
                if p[c - 1] == s[r - 1] or p[c - 1] == ".":
13
                    dp[r][c] = dp[r - 1][c - 1]
14
                elif c > 1 and p[c - 1] == "*":
15
                    if p[c - 2] == "." or s[r - 1] == p[c - 2]:
16
                        dp[r][c] = dp[r][c - 2] or dp[r - 1][c]
17
                    else:
18
                        dp[r][c] = dp[r][c - 2]
19
        return dp[n][m]