本文共 1111 字，大约阅读时间需要 3 分钟。

【解题思路】

9、10的为False

class Solution:    def isMatch(self, s: str, p: str) -> bool:        m, n = len(s) + 1, len(p) + 1        dp = [[False] * n for _ in range(m)]        dp[0][0] = True        # 初始化首行        for j in range(2, n, 2):            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'        # 状态转移        for i in range(1, m):            for j in range(1, n):                if p[j - 1] == '*':                    if dp[i][j - 2]: dp[i][j] = True                              # 1.                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.                else:                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.        return dp[-1][-1]'''作者：jyd链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/'''

• 复杂度分析：
  • 时间复杂度 O(MN) ： 其中 M, N 分别为 s 和 p 的长度，状态转移需遍历整个 dp 矩阵。
  • 空间复杂度 O(MN) ： 状态矩阵 dp 使用 O(MN)的额外空间。

转载地址：http://ifjii.baihongyu.com/