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]是否等于‘*’分为两类情况。
- p[j-1] !='*'情况较简单，利用递归的思想，我们求dp[i][j]时肯定已知dp[i-1][j-1]，我们只需要判断s[i-1]和p[j-1]的关系即可（这里注意i,j都是从1开始，字符串索引从0开始）
- p[j-1] =='*'情况又比较复杂。分析和代码如下：
这一题，如果不直接使用re模块，的确有点复杂，小詹只好像上边一步一步的拆开讲了，希望读者能够看得懂~完整代码可以省略一部分，先初始化所有情况为False，哪些分类中结果为false的即可省略。代码如下：
前十题，这一题怕是最难的了吧（如果不用re模块），运行结果如下：
