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

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正则表达式的方法快速解题,之后再分析其他方法吧,作弊方法如下:

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


那么问题来了,如果不允许使用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平面表示,我们列举出所有可能的情况进行分析!(整理比刷题还累,字丑勿嫌弃!)

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


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

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

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

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


第五种情况就要复杂点了,我们可以两层循环嵌套。先将第五种情况根据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] =='*'情况又比较复杂。分析和代码如下:
  3. Leetcode打卡 | No.010 正则表达式匹配

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

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

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


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

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

上一篇:Leetcode打卡 | No.011 盛最多水的容器


下一篇:Python 中的 sys.argv 是个什么鬼?