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

做了2个小时终于解出来了，使用dp来解，设dp[i][j]为str[0:i]和pattern[0:j]是否可以匹配，存放true或者false。

接着写状态转移方程：

$dp[i][j]=dp[i-1][j-1],ifstr[i-1]=pattern[j-1]dp[i][j]=dp[i-1][j-1],if\; \backslash \; str[i-1]=pattern[j-1]$

$dp[i][j]=false,ifstr[i-1]!=pattern[j-1]andpattern[j-1]!{=}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}dp[i][j]=false,\; if\; \backslash \; str[i-1]!=pattern[j-1]\; \backslash \; and\; \backslash \; pattern[j-1]\; !=\; \text{'}*\text{'}$

当pattern[j-1]=='*'时，需要进行下列三种情况的考虑：

$ifdp[i][j-2]==true,dp[i][j]=trueif\; \backslash \; dp[i][j-2]==true,dp[i][j]=true$

$ifpattern[j-2]==str[i-1]anddp[i-1][j]==true,dp[i][j]=trueif\; \backslash \; pattern[j-2]==str[i-1]\; \backslash \; and\; \backslash \; dp[i-1][j]==true,\backslash \; dp[i][j]=true$

$\mathrm{其}\mathrm{他}\mathrm{情}\mathrm{况}\mathrm{下}dp[i][j]\mathrm{都}\mathrm{是}false其他情况下dp[i][j]都是false$

代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
def getnum(s , tmp):
    if tmp=='.':
        return len(s)
    i = len(s)-1
    num=0
    while i >= 0:
        if s[i] == tmp:
            num+=1
            i-=1
        else:
            break
    return num

class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        # 初始化dp矩阵
        dp = [[True]*(len(pattern)+1) for _ in range(len(str)+1)]
        # 初始化边界条件
        for j in range(1,len(pattern)+1):
            if pattern[j-1]!='*':
                dp[0][j]=False
            else:
                if dp[0][j-2]==True:
                    dp[0][j] = True
                else:
                    dp[0][j] = False
        for i in range(1 , len(str)+1):
            dp[i][0] = False
        # 更新dp矩阵
        for i in range(1 , len(str)+1):
            for j in range(1 , len(pattern)+1):
                if str[i-1] == pattern[j-1] or pattern[j-1]=='.':
                    dp[i][j] = dp[i-1][j-1]
                elif pattern[j-1] != '*' :
                    dp[i][j] = False
                else:
                    tmp = pattern[j-2]
                    num = getnum(str[:i] , tmp)
                    tag = 0
                    for i_ in range(num+1):
                        if dp[i-i_][j-2] :
                            tag = 1
                    if tag==0:
                        dp[i][j] = False
        print(dp)
        if dp[len(str)][len(pattern)] == True:
            return True
        else:
            return False


str = "aaab" ; pattern = "a*a*a*c"
print(Solution().match(str , pattern))