给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
时间: 2023-05-04 20:01:43 浏览: 74
我来实现一个支持 '.' 和 '*' 的正则表达式匹配。
此问题是一道经典的动态规划题,可以使用递归或动态规划实现。
以下是动态规划的具体实现流程:
1. 初始化 dp 矩阵,dp[i][j] 表示 s 的前 i 个字符是否能被 p 的前 j 个字符匹配。
2. 初始化第一列,即当 p 为空字符串时,dp[i][0] 均为 False,因为非空字符串和空字符串无法匹配。
3. 初始化第一行,即当 s 为空字符串时,dp[0][j] 可以匹配的条件是 p 第 j 个字符为 '*',且 dp[0][j-2] 也为 True。
4. 遍历 dp 矩阵,当 s[i-1] 与 p[j-1] 匹配(或 p[j-1] 为 '.')时,有两种情况:
1) p[j-1] 不是 '*',此时 dp[i][j] 等价于 dp[i-1][j-1]。
2) p[j-1] 是 '*',此时有两种匹配情况:
a) '*' 作为 0 次使用,dp[i][j] 等价于 dp[i][j-2]。
b) '*' 作为 1 次或多次使用,此时 dp[i][j] 等价于 dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')。
5. 最终返回 dp[-1][-1],即 s 的全部字符是否能被 p 全部匹配。
代码如下:
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# 初始化第一列
dp[0][0] = True
for i in range(2, n + 1):
dp[0][i] = dp[0][i - 2] and p[i - 1] == '*'
# 遍历 dp 矩阵
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] = True
elif dp[i - 1][j] and s[i - 1] == p[j - 2] or p[j - 2] == '.':
dp[i][j] = True
elif dp[i - 1][j - 1] and s[i - 1] == p[j - 1] or p[j - 1] == '.':
dp[i][j] = True
return dp[-1][-1]