1益楼、題目
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p篡九，請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配章办。
'.' 匹配任意單個(gè)字符
'*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配带膜，是要涵蓋 整個(gè) 字符串 s的批狐，而不是部分字符串扇售。
2、代碼
class Solution(object):
def isMatch(self, s, p):
"""
使用一個(gè)二維數(shù)組dp來(lái)記錄字符串s的前i個(gè)字符和模式p的前j個(gè)字符是否匹配嚣艇。然后根據(jù)字符規(guī)律p中的字符進(jìn)行狀態(tài)轉(zhuǎn)移承冰，最終返回dp[m][n]，表示整個(gè)字符串s和模式p是否匹配食零，其中m為字符串s的長(zhǎng)度困乒，n為字符規(guī)律p的長(zhǎng)度。
"""
len_s, len_p = len(s), len(p)
dp = [[False] * (len_p + 1) for _ in range(len_s + 1)] # 字符串s的前i個(gè)字符和模式p的前j個(gè)字符是否匹配贰谣。
# 初始化
dp[0][0] = True
for j in range(1, len_p + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
# 狀態(tài)更新
"""
遍歷字符串s和模式p的所有字符娜搂，根據(jù)當(dāng)前字符的匹配情況進(jìn)行狀態(tài)更新。
如果當(dāng)前字符s[i - 1]和p[j - 1]相等吱抚，或者p[j - 1]為'.'百宇，則dp[i][j]取決于dp[i - 1][j - 1]，即s的前i-1個(gè)字符和p的前j-1個(gè)字符是否匹配秘豹。
如果p[j - 1]為'*'携御，則需要進(jìn)一步判斷：
如果s[i - 1]和p[j - 2]不相等，并且p[j - 2]也不是'.'，則'*'表示0個(gè)前面的字符啄刹，此時(shí)dp[i][j]取決于dp[i][j - 2]涮坐。
否則，''可以表示0個(gè)或多個(gè)前面的字符誓军。如果s[i - 1]和p[j - 2]相等袱讹，或者p[j - 2]為'.'，則dp[i][j]可以從兩種狀態(tài)轉(zhuǎn)移而來(lái)：要么''表示0個(gè)前面的字符（dp[i][j - 2]）昵时，要么'*'表示多個(gè)前面的字符（dp[i - 1][j]）捷雕。
"""
for i in range(1, len_s + 1):
for j in range(1, len_p + 1):
if s[i - 1] == p[j - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
if s[i - 1] != p[j - 2] and p[j - 2] != '.':
dp[i][j] = dp[i][j - 2]
else:
dp[i][j] = dp[i][j - 2] | dp[i - 1][j]
return dp[len_s][len_p]
3、示例
s=Solution()
ts='aab'
p='.*'
res=s.isMatch(ts,p)
print(res)
