Leetcode打卡 | No.010 正则表达式匹配

写在前边:

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!


No.10 正则表达式匹配

原题:

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.''*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

例如:

#示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 #示例 2: 输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。 #示例 3: 输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

题目分析:这一题怕是可以用python作弊噢哈哈哈!我们爬虫的时候可不就用过正则表达式嘛,这题的'.' 和'*'含义就正如python中的正则表达式,分分钟手到擒来嘛~然而小伙伴如果不允许使用re模块你会怎么做这一题?


首先给出利用python正则表达式的方法快速解题,之后再分析其他方法吧,作弊方法如下:

那么问题来了,如果不允许使用re模块呢?思考一分钟……

有一种叫做动态规划(DP)的方法,是每一步骤之间存在相关性时可使用的一种决策方法,有点类似递归的感觉。这里不做过多介绍,在放代码之前进行分析。

字符串s的每一个字符可记作s[i],字符模式p每一个字符记作p[j]。我们用dp[i][j]来表示s和p的匹配关系。不妨记dp[i][j] = true表示s[:i-1]和p[:j-1]可以实现正则匹配。

那么,字符串s和p的长度关系可以用一个i-j平面表示,我们列举出所有可能的情况进行分析!(整理比刷题还累,字丑勿嫌弃!)

上边的整理写的蛮清晰的(切片本质上时左闭右开,这里小詹为方便表示就当成双闭,即包括两个边界了,下同)!五种分类考虑到了所有的情况,小伙伴们可以在左侧平面图上标记,标记了五类就可以遍历整个i-j平面了。现在将上边情况依次用代码形式展示出来如下:

而第4种情况,比较interesting!由小詹的手写分析中可写出第四种情况如下:

第五种情况就要复杂点了,我们可以两层循环嵌套。先将第五种情况根据p[j-1]是否等于‘*’分为两类情况。

  1. p[j-1] !='*'情况较简单,利用递归的思想,我们求dp[i][j]时肯定已知dp[i-1][j-1],我们只需要判断s[i-1]和p[j-1]的关系即可(这里注意i,j都是从1开始,字符串索引从0开始)
  2. p[j-1] =='*'情况又比较复杂。分析和代码如下:

这一题,如果不直接使用re模块,的确有点复杂,小詹只好像上边一步一步的拆开讲了,希望读者能够看得懂~完整代码可以省略一部分,先初始化所有情况为False,哪些分类中结果为false的即可省略。代码如下:

前十题,这一题怕是最难的了吧(如果不用re模块),运行结果如下:

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励