LeetCode 刷题笔记 #10 正则表达式匹配
LeetCode 刷题笔记 #10 正则表达式匹配
昨天有提到今天这题是困难级别的，琢磨半天目前只弄了个耗时很久勉强完成任务的版本，明天再继续研究优化。
题目
中文题目
第 10 题 正则表达式匹配：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例：
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
说白了，就是让我们来设计实现正则表达式里的 "." 和 "*" 的逻辑。
思路
因为 "*" 可以匹配零个或多个前面的元素，也就是会改变 p 字符串长度的。那反过来想，如果 p 中没有星号，这就很简单了，p 和 s 等长，只要看对应位置上 p 中的字符要么为 "." 要么与 s 中字符相同，如果全符合，返回 True，否则 False。
接下来复杂些的是 p 中有 "*"，那既然有星号，那它最早也是出现在第二位也就是 p[1] 位置，出现在 p[0] 是没有意义的。如果它没出现在 p[1], 且 s[0] 和 p[0] 相同的话，那么我们可以把 p 和 s 的第一位同时删去来重新检测。也就是检测完第一位相同且 p[1] 不是星号，那么就可以调用 isMatch(s[1:],p[1:]) 来继续检测剩余子串。
但是如果 "*" 出现在了第二位：要么星号发挥的是 0 个之前字符的作用，这时就可以把 p 的前两位拿走重新与 s 来检测；要么星号是复制的前面那个字符，这时就可以把 s 的第一个字符拿走，用完整的 p 来继续检测 s[1:] 了。如果以上这两个条件可以一直达标且结果为 True，那么结果就是 True 了。
这里的主要思路就是在函数中删去前几位来继续调用 isMatch() 来对剩余子串进行检测。
代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# p 中有 * 的情况
if "*" in p:
# 检测 s 非空 且 p 首位要么与 s 相同、要么为 .
temp = s and p[0] in [".",s[0]]
# 对应思路中的 p[1] 为 *
if len(p)>1 and p[1]=="*":
return self.isMatch(s,p[2:]) or (temp and self.isMatch(s[1:],p))
# 对应 p[1] 不为 *
else:
return temp and self.isMatch(s[1:],p[1:])
# p 为空
elif p=="":
if s=="":
return True
else:
return False
# p非空，且不含 *
else:
if len(p)!=len(s):
return False
try:
for i,c in enumerate(p):
if c!="." and c!=s[i]:
print(c,s[i])
return False
return True
except:
return False
提交答案
这次提交答案，只追求能通过测试。
中文区结果：
解答错误 问题出在 s="ab" p=".*c" 上
英文版结果：
Runtime: 3152 ms, faster than 5.04% of Python3 online submissions for Regular Expression Matching. Memory Usage: 14 MB, less than 5.55% of Python3 online submissions for Regular Expression Matching.
这就有些奇怪了。。
结论
第十题，困难难度，勉强通过，还在研究，希望明天可以完成吧。