19. 正则表达式匹配

题目链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
难度：困难

描述：
请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

题解

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        r = [[False] * (n+1) for _ in range(m+1)]
        r[0][0] = True
        for i in range(0, m+1):
            for j in range(0, n+1):
                if j > 0:
                    if p[j-1] == "*":
                        if j >= 2:
                            r[i][j] |= r[i][j-2]
                        if i > 0 and j > 1 and (s[i-1] == p[j-2] or p[j-2] == "."):
                            r[i][j] |= r[i-1][j]
                    else:
                        if i > 0 and (s[i-1] == p[j-1] or p[j-1] == "."):
                            r[i][j] |= r[i-1][j-1]
        return r[m][n]