这是LeetCode的第10题，题目关于字符串的正则匹配，我们先来看题目相关信息：
Link
https://leetcode.com/problems/regular-expression-matching/
Difficulty
Hard
Description
Given an input string (s) and a pattern (p), implement regular expressionmatching with support for '.' and '*'.
'.' Matches any single character.'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).?
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like . or *.
题意
这道题属于典型的人狠话不多的问题，让我们动手实现一个简单的正则匹配算法。不过为了降低难度，这里需要匹配的只有两个特殊符号，一个符号是'.'，表示可以匹配任意的单个字符。还有一个特殊符号是'*'，它表示它前面的符号可以是任意个，可以是0个。
题目要求是输入一个母串和一个模式串，请问是否能够达成匹配。
Example 1:
Input:s = "aa"p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".Example 2:
Input:s = "aa"p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".Example 3:
Input:s = "ab"p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".Example 4:
Input:s = "aab"p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".Example 5:
Input:s = "mississippi"p = "mis*is*p*."
Output: false题解
这题要求的是完全匹配，而不是包含匹配。也就是说s串匹配完p串之后不能有剩余，比如刚好完全匹配才行。明确了这点之后，我们先来简化操作，假设不存在'*'这个特殊字符，只存在'.'，那么显然，这个简化过后的问题非常简单，我们随便就可以写出代码：
我们下面考虑加入'*'的情况，其实加入'*'只会有一个问题，就是'*'可以匹配任意长度，如果当前位置出现了'*'，我们并不知道它应该匹配到哪里为止。我们不知道需要匹配到哪里为止，那么就需要进行搜索了。也就是说，我们需要将它转换成一个搜索问题来进行求解。我们试着用递归来写一下：
这段代码的精髓在于，由于'*'之前的符号也可以是0个，所以我们不能判断当前位置是否会是'*'，而要判断后面一个位置是否是'*'。这句话看起来有些像是绕口令，但是却是这道题的精髓，如果看不懂的话，可以结合一下代码思考。
总之，就是以出否出现'*'为基点，分情况进行递归即可。
从代码上来看算上注释才12行，可是将这里面的关系都梳理清楚，并不容易。还是非常考验基本功的，需要对递归有较深入的理解才行。不过，这并不是最好的方法，因为你会发现有很多状态被重复计算了很多次。这也是递归算法经常遇到的问题之一，要解决倒也不难，我们很容易发现，对于固定的i和j，答案是固定的。那么，我们可以用一个数组来存储所有的i和j的情况。如果当前的i和j处理过了，那么直接返回结果，否则再去计算。
这种方法称作记忆化搜索，说起来复杂，但是实现起来只需要加几行代码：
如果你对动态规划足够熟悉的话，想必也应该知道，记忆化搜索本质也是动态规划的一种实现方式。但同样，我们也可以选择其他的方式实现动态规划，就可以摆脱递归了，相比于递归，使用数组存储状态的递推形式更容易理解。
我们用dp[i][j]存储s[:i]与p[:j]是否匹配，那么根据我们之前的结论，如果p[j-1]是'*'，那么dp[i][j]可能由dp[i][j-2]或者是dp[i-1][j]转移得到。dp[i][j-2]比较容易想到，就是'*'前面的字符作废，为什么是dp[i-1][j]呢？这种情况是代表'*'连续匹配，因为可能匹配任意个，所以必须要匹配在'*'这个位置。
举个例子：
s = 'aaaaa'
p = '.*'
在上面这个例子里，'.'能匹配所有字符，但是问题是s中只有一个a能匹配上。如果我们不用dp[i-1][j]而用dp[i-1][j-1]的话，那么是无法匹配aa或者aaa这种情况的。因为这几种情况都是通过'*'的多匹配能力实现的。如果还不理解的同学， 建议仔细梳理一下它们之间的关系。
我们用数组的形式写出代码：
这题的代码并不长，算上注释也不过20行左右。但是当中对于题意的思考，以及对算法的运用很高，想要AC难度还是不低的。希望大家能够多多揣摩，理解其中的精髓，尤其是最后的动态规划解法，非常经典，推荐一定要弄懂。当然如果实在看不明白也没有关系，在以后的文章，我会给大家详细讲解动态规划算法。
今天的文章就到这里，如果觉得有所收获，请顺手点个关注或者转发吧，你们的支持是我最大的动力。