LeetCode算法 —— 正则表达式匹配（详解官方递归思想）
这个题目我想了一天也没有做出来，一直是单调的字符串处理思想解题，导致后期各种 bug
好在我知难而退，看了一波大家的题解，觉得递归的那个题解非常的有趣. . .动态规划接触过，但没有仔细的研究过（图论算法的最短路径中有过），暑假再学习吧
图论算法动态规划相关文章： 《算法笔记》—— 图 “最短路径” 之 Floyd-Warshall算法、Diljkstra算法
.原题解链接：
此文章会用断点跟踪递归过程 . . .
题目：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例此外就不粘贴了
代码如下：↓ ↓ ↓
代码中三处使用递归，我在图片用红色框框标明了，并且我在其中都加了注释，应该是对的 ^ _ ^ . . .
递归思想：
将两个字符串，s 和 p 依次的减少，再
减少的过程不断的判断是否满足 正则表达式的要求. . .
第一处递归：↓ ↓ ↓
在判断的过程中， 类似 a* 这样的子串可能不需要，所以直接放弃 a*，这种情况应该只要有 * 这样的子串都需要判断
（这也是递归的一种复杂度的体现） . . . （a* 是一个整体） . . .
第二处递归：↓ ↓ ↓
其实这里的 “
被忽略” 一词用的并不是太好，很容易对像我这样菜的人造成误解
这里的意思是p[0] 成功匹配了 s[0]，对 s的下一个子串（成功的过滤掉）再次进行匹配判断（判断过程中会再次进行其它的再次递归，递归到最后会反回来（也就是所谓的回溯思想） . . .
.
下面我会慢慢的调试递归的每一步的变化 . . .
第三处递归：↓ ↓ ↓
这个就是没有 * 号的情况下判断 s[0] 和 p[0] 是否相同，相同则截取两个串下一个 -1 的字串，再次进行递归判断 . . .
…
大家在思考的过程会发现，这个递归原理会造成大量的无用功，不管是时间，还是空间，都提升了大量的复杂度所以能用动态规划就尽量使用动态规划 . . .
…
.
带你走进递归的世界 ↓ ↓ ↓
下面我们来对下面这个数据进行测试：
-
定位到开始的第一条语句：
-
p[1] == ‘*’，进行对应的递归函数：
此时，p == "". . . 但是 s不等于空，所以直接返回 false 到 如下这个地方： -
p[0] 与 s[0] 相等，进入下面的递归函数：
此时 s == “aaa”，p == “a*” . . . -
重复
第二步与第三步，直至 s 与 p 都为空 返回 true：
s 与 p 的变化如下所示 ↓ ↓ ↓
这次数据测试很有趣，因为它没有进行第三种递归形式，问题进行 第一个和第二个递归，原因是 a * 中的 * 起的作用 . . .
大家可以手动测试其它的数据，看看其它数据是如何运行的呢 ^ _ ^
.