给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "ab" p = "."
输出：true
解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 2：
输入：s = "aab" p = "cab"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
解法
这个题确实比较难，自己昨天没看答案，花了好几个小时也没有做出来，总有最后几个通过不了测试。也想过用动态规划来做，但是不知道怎么推出动态转移方程，所以采用了双指针的做法，但是没有做出来。
力扣的官方答案不太好理解，最后还是参考了力扣的一个精选视频，才完全搞懂，以后碰到不好推出动态转移方程的，可以直接弄一张表，自己先填写一下，填着填着就能发现规律了。
填写完成过后的截图
代码如下，附有详细的注释，结合着这张图看代码一定会瞬间明白的：
def isMatch2(s, p):
m, n = len(s), len(p)
# 初始化二维数组，以 " "+p 为行的头，以" "+s为列的头
# 如果s和p完全匹配，那么它们两个头部加上一个" "空字符也同样匹配
# 之所以加一个空字符，是为了方便初始化，即第一行即为初始条件
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True # 最左上角，因为都是两个空串，所以匹配，为True
# 初始化p与空串的匹配，即先填写第一行，初始条件
for col in range(1, n + 1):
# 即从p的第二位开始
if col > 1:
# 如果当前为*号，那么它的状态值就等于左边第二位的状态值
# 因为前面加了一个空字符，所以p的当前字符下标都要减1，s与p相同
if p[col - 1] == "*":
dp[0][col] = dp[0][col - 2]
else:
dp[0][col] = False
else:
# 这里其实是col等于1的时候，也就是p的第一位字符
# 因为p不会以"*"或者" "开头，所以肯定不会走到这个else里面来
# dp[0][1]肯定等于False，这个else可以省略
if p[col - 1] == "*":
dp[0][col] = True
# 开始填表，从dp[1][1]开始每行每行的开始填表
for row in range(1, m + 1):
for col in range(1, n + 1):
# 如果p的当前字符为"."或者等于s的当前字符
# 那么它的状态值就取决于它左上角的状态值
# 而且p的当前字符肯定不为"*"
if p[col - 1] == s[row - 1] or p[col - 1] == ".":
dp[row][col] = dp[row - 1][col - 1]
elif p[col - 1] == "*": # p的当前字符为"*"的情况下
# 因为"*"不可能出现在p的第一位，所以其实下面的col>1的判断可以省略
if col > 1:
# 当p的当前位为"*"号时，如果p的当前左边第二位也和s的当前位匹配，那么p的当前位也匹配
# 也就是 "*"前面字符出现0次的情况
if dp[row][col - 2]:
dp[row][col] = True
# 如果p当前的前一位字符为"."或者等于s的当前字符
# 那么当前位置的状态就等于它上面第一个位置的状态
# 这也是 "*"前面字符出现多次的情况
elif p[col - 2] in {s[row - 1], "."}:
dp[row][col] = dp[row - 1][col]
# 返回填表后最右下角的值，即为整个p和s的匹配情况
return dp[m][n]
复杂度分析
- 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 p 的长度。我们需要计算出所有的状态，并且每个状态在进行转移时的时间复杂度为O(1)。因为我们是从dp[1][1]开始填的，所以时间复杂度还是O(mn)。
- 空间复杂度：O((m+1)(n+1))，即为存储所有状态使用的空间。因为s和p前面都加了一个空字符，所以空间复杂度是O((m+1)(n+1))。
网友评论