1、题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
2、代码
class Solution(object):
def isMatch(self, s, p):
"""
使用一个二维数组dp来记录字符串s的前i个字符和模式p的前j个字符是否匹配。然后根据字符规律p中的字符进行状态转移，最终返回dp[m][n]，表示整个字符串s和模式p是否匹配，其中m为字符串s的长度，n为字符规律p的长度。
"""
len_s, len_p = len(s), len(p)
dp = [[False] * (len_p + 1) for _ in range(len_s + 1)] # 字符串s的前i个字符和模式p的前j个字符是否匹配。
# 初始化
dp[0][0] = True
for j in range(1, len_p + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
# 状态更新
"""
遍历字符串s和模式p的所有字符，根据当前字符的匹配情况进行状态更新。
如果当前字符s[i - 1]和p[j - 1]相等，或者p[j - 1]为'.'，则dp[i][j]取决于dp[i - 1][j - 1]，即s的前i-1个字符和p的前j-1个字符是否匹配。
如果p[j - 1]为'*'，则需要进一步判断：
如果s[i - 1]和p[j - 2]不相等，并且p[j - 2]也不是'.'，则'*'表示0个前面的字符，此时dp[i][j]取决于dp[i][j - 2]。
否则，''可以表示0个或多个前面的字符。如果s[i - 1]和p[j - 2]相等，或者p[j - 2]为'.'，则dp[i][j]可以从两种状态转移而来：要么''表示0个前面的字符（dp[i][j - 2]），要么'*'表示多个前面的字符（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)
