解题思路

「二维表」动态规划
具体详见代码里面的注释
https://leetcode-cn.com/problems/regular-expression-matching/

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        rows, columns = len(s) + 1, len(p) + 1
        matrix = [[False for _ in range(columns)][:] for _ in range(rows)]
        for r in range(rows):
            for c in range(columns):
                if r == c == 0:  # 空串空模式
                    matrix[r][c] = True
                elif r == 0:  # 仅空串
                    matrix[r][c] = p[c-1] == '*' and matrix[r][c-2]
                elif c == 0:  # 仅空模式
                    matrix[r][c] = False
                else:  # 有串有模式
                    if p[c-1] in ['.', s[r-1]]:
                        matrix[r][c] = matrix[r-1][c-1]
                    elif p[c-1] == '*':
                        if p[c-2] in ['.', s[r-1]]:
                            # 1.字符串进一格，模式进两格
                            # 2.字符串进一格，模式保持不变
                            # 3.字符串保持不变，模式进两格
                            matrix[r][c] = matrix[r-1][c-2] or matrix[r-1][c] or matrix[r][c-2]
                        else:
                            matrix[r][c] = matrix[r][c-2]
                    else:
                        matrix[r][c] = False
        return matrix[len(s)][len(p)]