10.正则表达式匹配

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 判空（结束）
        if not s and not p:
            return True
        elif s and not p:
            return False
        # s 第一列表示 s 的 ^
        dp = [[False] * (len(s) + 1) for i in range(len(p))]
        # 处理第一列
        if len(p) > 1:
            dp[1][0] = p[1] == '*'
        for y in range(2, len(p)):
            if not dp[y - 1][0] and not dp[y - 2][0]:
                break
            dp[y][0] = p[y] == '*'
        # 处理第一行剩下的部分
        if s:
            dp[0][1] = p[0] == s[0] or p[0] == '.'
        for y in range(1, len(p)):
            for x in range(1, len(s) + 1):
                # 先横再竖
                if p[y] == '*':
                    # 上方为 T 或上上为 T 必为 T，上为 T 表示这里 * 代表 1，上为 F 上上为 T 表示这里 * 为 0
                    if dp[y - 1][x] or dp[y - 2][x]:
                        dp[y][x] = True
                    # 其余情况首先左为 T，然后看看上一个 p 是不是能匹配当前的 s，左为 T 说明这里的 * 为 > 2，要检测能否继续匹配
                    elif dp[y][x - 1] and (p[y - 1] == '.' or p[y - 1] == s[x - 1]):
                        dp[y][x] = True
                elif p[y] == '.':
                    # 如果左上是 T 那么这里必为 T，s 和 p 都向后移动匹配下一个字符，反过来需要前面的能匹配上
                    if dp[y - 1][x - 1]:
                        dp[y][x] = True
                else:
                    # 普通字符的时候如果左上方已经为 F 则必为 F，同 .，s 和 p 都向后移动匹配下一个字符，反过来需要前面的能匹配上
                    if dp[y - 1][x - 1] and p[y] == s[x - 1]:
                        dp[y][x] = True
        return dp[-1][-1]