剑指 Offer 19. 正则表达式匹配

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

感觉题意其实蛮难理解的。截个图：

是比较复杂的动态规划，做了下笔记和注释。

class Solution:

    def isMatch(self, s: str, p: str) -> bool:

        # 要判断字符串是否匹配，可以用动态规划进行判断

        # dp[i][j]对应s[i-1]和p[j-1]对应的字符串是否匹配。

        # ①p[j-1]=='*'

        # 1.视作p字符串倒数第二个字符出现了零次，则不需要判断是否相等了。

        # eg:s[]=abcde

        # p[]=abcdf*e 此时f*视作f出现零次

        # 这个情况下：dq[i][j]=dp[i][j-2]

        # 2.视作p字符串倒数第二个数出现了两次

        # eg:s[]=abcdd

        # p[]=abcd* 此时d*视作d出现了两次

        # 3..代表任意字符，并出现了两次

        # eg:s[]=abc

        # p[]=abc.* 此时.*视作为空

        # ②p[j-1]!='*'

        # 1.d[i-1][j-1]并且s[i-1]=p[j-1]

        # eg:s[]=abcde

        # p[]=abcde

        # 2.d[i-1][j-1]并且p[j-1]

        # eg:s[]=abcde

        # p[]=abcd. 此时.视作e，可以匹配

        # ③初始化的时候

        # dp[0][0]=0

        # 并且当p偶数位为'*'时，可以视作出现0次，所以p如果为偶数位都为*时，可以匹配空字符串

        m=len(s)+1

        n=len(p)+1

        dp=[[False for col in range(n)]for row 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

                    elif dp[i-1][j] and s[i-1]==p[j-2]:dp[i][j]=True

                    elif dp[i-1][j] and p[j-2]=='.':dp[i][j]=True

                else:

                    if dp[i-1][j-1] and s[i-1]==p[j-1]:dp[i][j]=True

                    elif dp[i-1][j-1] and p[j-1]=='.':dp[i][j]=True

        return dp[m-1][n-1]