题解 | #正则表达式匹配#

class Solution:
    def match(self, str, pattern) -> bool:
        # write code here
        m = len(str)
        n = len(pattern)
        array = [[False] * (n + 1) for _ in range(m + 1)]  # 创建数组，行、列分别加入一个空字符
        array[0][0] = True
        for z in range(1, n + 1):  # 初始化array数组中str的空字符这一行，即第0行
            if pattern[z - 1] == "*":  # str的空字符这一行遇到*时，可以丢弃x*,取z-2的值，遇到字母或”.“时为false
                array[0][z] = array[0][z - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if pattern[j - 1] == "*":  # 当遇到*时，分以下两种情况讨论，即当前字符与*前一个字母是否相等
                    if (
                        str[i - 1] == pattern[j - 2] or pattern[j - 2] == "."
                    ):  # 当前字符与*前一个字母x相等(即array[i-1])，可保留x*,也可丢弃x*(即array[i][j-2])
                        array[i][j] = array[i - 1][j] | array[i][j - 2]
                    else:  # 当前字符与*前一个字母x不相等，只能丢弃x*(即array[i][j - 2])
                        array[i][j] = array[i][j - 2]
                else:  # 未遇到*，即字母或”.“
                    if str[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
                        array[i][j] = array[i - 1][j - 1]
        print(array)
        return array[m][n]
	  #总结思路：
	  #1.构造动态规划中暂存数据的二维矩阵array[][]，行数为str+1，列为pattern+1，行列各加了1，是为了给首行和首列添加一个空字符，方便动态规划的状态转移
	  #2.初始化第一行的值，把第一行做为状态转移的初始位置，所以第一行必须要有初始值。初始值分两部分，一部分是array[0][0]=True,array[0][1]到array[0][-1]分情况讨论并开始进行状态转移来赋值，情况一：遇到字母和“.”array[0][x]存值false，情况二：遇到“*”array[0][x]存array[]0[x-2]的值，即丢弃掉*和*的前一个字符
	  #3.有了第一行的值后，便可正式开始进行动态规则，嵌套循环遍历二维数组array（由于2步骤中已初始化了第一行，故此处不必遍历第一行，从第二行开始遍历），当循环至i,j时，开始分两类情况讨论，一是str[i-1]遇到了匹配模式中的普通字母或"."，此时很好比较，若匹配成功array[i][j]就存array[i-1][j-1]的值即可；二是str[i-1]遇到了匹配模式中的“*”，此时又得分情况讨论，若str[i-1]与“*”的前一个字符匹配（注意匹配是指包括字母相等或pattern[j-1]为“.”），此时可以舍去*和*的前一个字符（array[i][j]=array[i][j-2]），也可以保留*和*的前一个字符（array[i][j]=array[i-1][j]）,若str[i-1]与“*”的前一个字符不匹配，只能舍去*和*的前一个字符（array[i][j]=array[i][j-2]）。
	  #4.最后，输出array[m][n]即可，本题注意：1.构造二维数组，2.初始化二维数组时也需要使用动态规划来初始化3.正式进行状态转移时要分情况讨论，第一层情况是是否遇到了“*”，若遇到“*”又得分两种情况。