一刷~
给你一个字符串
s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串
s的，而不是部分字符串。
有几个用例超时，容我三思。
目前的思路：递归判断是否满足匹配条件。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if len(s) == 0 and len(p) == 0:
return True
if len(s) == 0 and len(p) > 1 and p[1] == "*":
return self.isMatch(s, p[2:])
if len(s) * len(p) == 0:
return False
if len(p) == 1:
if p[0] == ".":
return len(s) == 1
else:
return len(s) == 1 and s[0] == p[0]
else:
if p[1] == "*":
if p[0] == ".":
return self.isMatch(s, p[2:]) or self.isMatch(s[1:], p)
else:
return self.isMatch(s, p[2:]) or (s[0] == p[0] and self.isMatch(s[1:], p))
else:
if p[0] == ".":
return self.isMatch(s[1:], p[1:])
else:
return p[0] == s[0] and self.isMatch(s[1:], p[1:])
定睛一看s、p的长度都不超过20，想到用二维动态规划，果然过了，但是动态方程推导过程蛮坎坷的，两个小时过去了- -
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[0]*(n+1) for i in range(m+1)]
dp[0][0] = 1
for i in range(1, n+1):
if p[i-1] == "*":
dp[0][i] = dp[0][i-2]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == "*":
if dp[i][j-2]:
dp[i][j] = 1
continue
if p[j-2] == ".":
if dp[i-1][j]:
dp[i][j] = 1
else:
if s[i-1] == p[j-2] and dp[i-1][j]:
dp[i][j] = 1
elif p[j-1] == ".":
dp[i][j] = dp[i-1][j-1]
else:
if s[i-1] == p[j-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n] == 1
