1
# Runtime: 1580 ms (Top 22.92%) | Memory: 22.4 MB (Top 66.92%)
2
class Solution:
3
    def isMatch(self, s: str, p: str) -> bool:
4
        m = len(s)
5
        n = len(p)
6

7
        dp = [[False] * (n + 1) for i in range(m + 1)]
8

9
        dp[0][0] = True
10

11
        for j in range(len(p)):
12
            if p[j] == "*":
13
                dp[0][j + 1] = dp[0][j]
14

15
        for i in range(1, m + 1):
16
            for j in range(1, n + 1):
17
                if p[j - 1] == "*":
18
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
19

20
                elif s[i - 1] == p[j - 1] or p[j - 1] == "?":
21
                    dp[i][j] = dp[i - 1][j - 1]
22

23
        return dp[-1][-1]