剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列
程序员文章站
2022-04-23 22:17:35
...
点击专辑上方“蓝字”关注我吧
题目难度: 困难
原题链接[1]
今天继续更新剑指 offer 系列, 这道题是这个系列的第一道困难题, 也是非常经典的题目了
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
请实现一个函数用来匹配包含.
和*
的正则表达式。模式中的字符.
表示任意一个字符,而*
表示它前面的字符可以出现任意次(含 0 次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"
与模式"a.a"
和"ab*ac*a"
匹配,但与"aa.a"
和"ab*a"
均不匹配。
题目样例
示例 1
输入
s = "aa"
p = "a"
输出
false
解释
"a" 无法匹配 "aa" 整个字符串。
示例 2
输入
s = "aa"
p = "a*"
输出
true
解释
因为 *
代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3
输入
s = "aab"
p = "c*a*b"
输出
true
解释
因为 *
表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
题目思考
- 如何特殊处理
.
和*
?
解决方案
思路
分析
- 分析题目, 特殊字符只有
.
和*
..
比较简单, 直接可以跟任何字符匹配; 而*
则要考虑前一个字符是什么. - 要判断两个字符串是否匹配, 最简单的做法就是双指针依次比较即可, 这里也不例外.
- 我们需要维护当前
s
和p
的下标i
和j
, 然后从起点开始匹配, 分为以下几种情况分析:
- 如果
p[j+1]
存在且为*
: 此时s[i]
可以直接跳到与p[j+2]
匹配, 表示不用当前的x*
组合; 当然也可以j
不动而i
继续后移 (前提是s[i]
和p[j]
匹配) - 否则的话意味不能跳过, 必须比较
s[i]
和p[j]
, 只有p[j]
为.
或者和s[i]
相等时才成功匹配.
- 边界情况 1:
p
的字符已经用完, 即j == len(p)
. 此时只有当s
也恰好匹配完, 才表明两个字符串匹配; - 边界情况 2:
s
的字符已经用完, 即i == len(s)
. 这种情况下, 如果p
也恰好匹配完显然匹配; 但p
没有用完的时候也可能匹配. 这是因为有*
的存在, 它和它前一个字符可以只匹配 0 次, 这就意味着只有当前p
之后的字符串满足x*x*
这样的形式就也可以匹配; - 此时
p
和s
的字符都还有剩余, 这时候不能简单比较s[i]
和p[j]
, 这是因为有*
的存在, 需要继续细分为两种情况:
(i, j)
组合的结果保存起来, 避免重复计算, 这就是记忆化搜索的思想
实现
- 下面代码完全基于上述分析实现, 必要步骤都有详细注释
复杂度
- 时间复杂度
O(MN)
- 采用了记忆化方法, 每个字符只需要计算一次匹配
- 空间复杂度
O(MN)
- 需要存所有下标组合的匹配结果
代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# 记忆化搜索
memo = {}
def match(i, j):
# 如果(i, j)已经在memo中就不要重复计算了
if (i, j) not in memo:
if j == len(p):
# 模式串p遍历完了, 那么只有当s正好也遍历完才满足要求
memo[i, j] = i == len(s)
elif i == len(s):
# 此时意味着s遍历完了, 但模式串p仍然有值, 这时候只有当后面的模式串都是x*x*这样的形式才可以, 代表后面的x*都只匹配0次
# 所以需要判断p[j+1]是否是*, 是的话继续递归判断(i,j+2)组合, 否则直接返回False
if j + 1 and p[j + 1] == '*':
memo[i, j] = match(i, j + 2)
else:
memo[i, j] = False
else:
# 意味着s和p都没遍历完
if j + 1 and p[j + 1] == '*':
# 下一个p字符是*, 意味着当前字符可以不使用, 首先考虑这种情况
memo[i, j] = match(i, j + 2)
if s[i] == p[j] or p[j] == '.':
# 但如果当前字符恰好匹配的话, 也可以使用它, j位置保持不变, i后移
memo[i, j] |= match(i + 1, j)
else:
# 下一个p字符不是*, 必须老老实实根据当前字符匹配了
memo[i, j] = (s[i] == p[j] or p[j] == '.') and match(
i + 1, j + 1)
return memo[i, j]
return match(0, 0)
参考资料
[1]原题链接: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
你的每个赞和在看,我都喜欢!推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer13:数组[奇数,偶数],奇数偶数相对位置不变。
-
剑指offer第二天
-
剑指offer JZ31 整数中1出现的次数 Python 解