剑指 正则表达式匹配

通过动态规划方式去解决, 一位一位进行比较，dp数组中的状态记录的是s的i到p的j是否是匹配的。其中dp[0][j]的状态通过偶数位置是不是"*"来判断，其他的判断当前字符是不是"*"如果是的话，要么把当成前面的字母出现了0次，要么当成前面的字母出现了1次或多次，所以要么看dp[i][j-2]的状态，要么当s[i-1]==p[i-1]的时候，去看dp[i-1][j]的状态，因为如果是看成出现多次的话，总会转移到最后一位的状态这个时候看dp[i][j-2]的状态就可以了。
当当前字母不是""的时候，看s[i-1]==p[j-1] 或者p[j-1]=="."，这个时候就看dp[i-1][j-1]的状态就可以了。

ps. |=按位或赋值 x |= y x = x | y

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(p) + 1
        n = len(s) + 1
        dp = [[False] * m for _ in range(n)]
        dp[0][0] = True#  注意要在dp[0][i]赋值之前就初始化dp[0][0]
        # 初始化首行
        for j in range(2, m, 2):
            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
        # 首列一定为False，也不用专门初始化了

        for i in range(1, n):
            for j in range(1, m):
                if p[j-1]!='*':
                    if s[i-1]==p[j-1]:
                        dp[i][j]=dp[i-1][j-1]
                    elif p[j-1]=='.':
                        dp[i][j]=dp[i-1][j-1]

                else:
                    if j>=2 and( p[j-2]==s[i-1] or p[j-2]=='.'):
                        dp[i][j]=dp[i-1][j]
                    if j>=2 and dp[i][j]!=True:
                        dp[i][j]=dp[i][j-2]

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