动态规划 | #正则表达式匹配#

class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        #######################将*和.或者a-z结合在一起进行分割############################
        self.str = list('aaa'+pattern+'---')  # 序列padding，避免空字符、单字符等特殊情况处理
        self.pattern = list('aaa'+str+'---')
        iii = 0
        while self.str[iii] != '-':
            if self.str[iii+1] == '*':
                self.str[iii] += '*'
                del self.str[iii+1]
            iii += 1
        iii = 0
        while self.pattern[iii] != '-':
            if self.pattern[iii+1] == '*':
                self.pattern[iii] += '*'
                del self.pattern[iii+1]
            iii += 1
        n = len(self.str)
        m = len(self.pattern)


        #######################动态规划求解############################
        dp_arr = [[0 for _ in range(m)] for __ in range(n)]
        dp_arr[0][0] = dp_arr[1][1] = dp_arr[2][2] = 1
        pre_st = 3
        for i in range(2, n):
            cur_st = 2
            if self.str[i] == '.*': # 通配符，直接秒杀这一行，进入下一行
                dp_arr[i][pre_st:] = [1]*(m-pre_st)
                continue
            for j in range(pre_st, m):
                if not (dp_arr[i-1][j] or dp_arr[i-1][j-1] or dp_arr[i][j-1]): break  # 如果↑、↖、←元素都为0，当前元素失去了匹配基础，直接跳到下一行
                # 以下三个if，只要有一个给dp_arr赋1，则不进入下一个if
                if dp_arr[i-1][j]:  # ↑方向已有匹配，新的str[i]要匹配的话只能变成''空字符，也只有带*的字符符合条件
                    dp_arr[i][j] = int('*' in self.str[i])
                if (not dp_arr[i][j]) and dp_arr[i-1][j-1]:  # ↖已有匹配，新的str[i]要匹配的话1、pattern[i]等于str[i]，2、等于带星号str[i]的数字部分，3、str[i]为'.'
                    dp_arr[i][j] = int((self.pattern[j] in self.str[i]) or ('.' in self.str[i]))
                if (not dp_arr[i][j]) and dp_arr[i][j-1] and '*' in self.str[i]:  # ←已有匹配，新的str[i]要匹配的话，当前str[i]必须带星号而且pattern[j-1]等于pattern[j]和str[i]的数字部分
                    dp_arr[i][j] = int(self.pattern[j] == self.pattern[j-1] and (self.pattern[j] in self.str[i]))
                if dp_arr[i][j] and cur_st==2:  # 记录当前行第一个变为1的列号，作为下一行的起点，节省时间
                    cur_st = j
            pre_st = cur_st*1

        print(*dp_arr, sep='\n')
        return dp_arr[n-1][m-1]
                
                    

str1 = 'aaa'   
str2 = 'ab*a'     

print(Solution().match(str1, str2))



             

# 动态规划思路

# 1. 构建状态，定义pattern当前元素pattern[i]和str当前元素str[j]是否匹配为当前状态。

# 2. 构造一个n*m的表格，对于某一个状态，是否匹配取决于↑↖←三个相邻表格，状态转移方法如下：

# - ↑已经匹配的话，要匹配当前点，则pattern[i]只能为空字符；

# - ↖已经匹配的话，pattern[i]必须能匹配str[i]；

# - ←已经匹配的话，pattern[i]必须是一个char*，且str[j]要等于char。

# 以上三个条件任意满足一个即可，我们不需要关心匹配上的pattern会退化为什么形式（比如A*退化为AAA），因为接下来的匹配不会关心这件事

# 3. 如果最后表格最后一个元素能匹配，返回True