今天分享的题目来源于 LeetCode 上第 10 号问题：正则表达式匹配。题目难度为
Hard
，目前通过率为 23.9% 。
温馨提示
：本题目有点难，干货有点干，建议先收藏后再仔细阅读。
题目描述
给你一个字符串
s
和一个字符规律
p
，请你来实现一个支持
'.'
和
'*'
的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖
整个
字符串
s
的，而不是部分字符串。
说明:
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
题目解析
这道题其实是要实现 Regular Expression 里面的两个符号，一个是 '.'，另一个是 '*'， 前者表示可以 match 任意一个字符，后者表示其前面的字符可以重复零次或者多次。
题目的难点其实是在于 * 上面，如果没有这个 *，题目会变得非常简单，这里说一下题目的两个隐含条件：
当然你也可以把这两个隐含条件当作一个来看，不管如何，我们的代码实现必须建立在这个基础之上，否则，case 考虑多了，题目将无从下手。
解法一：递归暴力求解
递归方式的暴力深度优先搜索求解方法往往是搜索问题的万金油，
这里你只需要简单的考虑两件事情，一是这个问题是否可以划分为子问题，二是每个子问题有几种状态，就是在当前考虑的问题下，一共有多少种可能性
。
知道了这两点后，对于每个子问题的每一个状态递归求解就行。
上面说的可能有点抽象，结合这个题目来做例子，这里的问题是，输入一个字符串 s，以及其匹配字符串 p，要求解这两个字符串是否匹配。
我们首先考虑这个字符串比较的问题能不能划分为一个个的子问题，你发现
字符串是可以划分成为一个个字符的，这样字符串比较的问题就会变成字符的比较问题
，这样一来，我们就可以把问题看成，决定 s[i,…n] 是否能够匹配 p[j,…m] 的条件是子问题 s[i+1,…n] 能不能够匹配 p[j+1,…m]，另外还要看 s[i] 和 p[j] 是否匹配，但是这里的当前要解决的问题是 s[i] 和 p[j] 是否匹配，只有这一点成立，我们才有继续递归去看 s[i+1,…n] 是匹配 p[j+1,…m]，注意这里我说 s[i] p[j]， 并不表示说当前就只用考虑这两个字符之间匹不匹配，它只是用来表示当前问题，这个当前问题也许只需要比较一个字符，也许要比较多个，这就引申出了前面提到的第二点，我们还需要考虑当前问题中的状态。
对于字符串 s 来说，没有特殊字符，当前问题中字符只会是字母，但是对于 p 来说，我们需要考虑两个特殊符号，还有字母，这里列举所有的可能，如果说当前的子问题是 s[i,…n] 和 p[j…m]:
-
s[i] == p[j]，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]
-
p[j] == '.'，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]
-
p[j+1] == '*'，s[i] != p[j]，子问题成立与否取决于子问题 s[i,…n] 和 p[j+2,…m]
-
p[j+1] == '*'，s[i] == p[j]，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j,…m]
这里我解释下第三种情况，之前在题目描述里说过，p 的起始字符不可能是 *，也就是说 * 的前面必须有字母，根据定义，这里我们可以把 * 的前面的元素个数算作是零个，这样我们就只用看，s[i,…n] 和 p[j+2,…n] 是否匹配，如果算作一个或者多个，那么我们就可以看 s[i+1,…n] 和 p[j,…m] 是否成立，当然这个的前提是 p[j] == s[i] 或者 p[j] == '.'， 我们可以结合代码来看看
class Solution {
public boolean isMatch(String s, String p) {
if (s.equals(p)) {
return true;
}
boolean isFirstMatch = false;
if (!s.isEmpty() && !p.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
isFirstMatch = true;
}
if (p.length() >= 2 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2))
|| (isFirstMatch && isMatch(s.substring(1), p));
}
return isFirstMatch && isMatch(s.substring(1), p.substring(1));
}
}
上面的实现之所以被称为暴力求解是因为子问题的答案没有被记录，也就是说如果当前要用到之前的子问题的答案，我们还得去计算之前计算过的子问题。
解法二：记忆化搜索
上面的暴力解法是因为没有记录答案，记忆化搜索是在 “傻搜” 的基础之上添加 “记事本”。这里我把递归的方向给改变了，当然这不是必要的，主要想说明，对于递归来说，从后往前考虑和从前往后考虑都是可行的。
我们假设当前问题是考虑 s 的第 i 个字母，p 的第 j 个字母，所以这时的子问题是 s[0…i] 和 p[0…j] 是否匹配
：
-
p[j] 是字母，并且 s[i] == p[j]，当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j-1] 是否成立
-
p[j] 是 '.'，当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j-1] 是否成立
-
p[j] 是字母，并且 s[i] != p[j]，当前子问题不成立
-
p[j] 是 '*'，s[i] == p[j - 1]，或者 p[j - 1] == '.'， 当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j] 是否成立
-
p[j] 是 '*'，s[i] != p[j - 1]，当前子问题正确与否取决于子问题 s[0…i] 是否匹配 p[0,…j-2]
不管是从前往后，还是从后往前，你可以看到，考虑的点都是一样的，只是这里我们多加了一个 “记事本”
public boolean isMatch(String s, String p) {
if (s.equals(p)) {
return true;
}
boolean[] memo = new boolean[s.length() + 1];
return helper(s.toCharArray(), p.toCharArray(),
s.length() - 1, p.length() - 1, memo);
}
private boolean helper(char[] s, char[] p, int i, int j, boolean[] memo) {
if (memo[i + 1]) {
return true;
}
if (i == -1 && j == -1) {
memo[i + 1] = true;
return true;
}
boolean isFirstMatching = false;
if (i >= 0 && j >= 0 && (s[i] == p[j] || p[j] == '.'
|| (p[j] == '*' && (p[j - 1] == s[i] || p[j - 1] == '.')))) {
isFirstMatching = true;
}
if (j >= 1 && p[j] == '*') {
boolean zero = helper(s, p, i, j - 2, memo);
boolean match = isFirstMatching && helper(s, p, i - 1, j, memo);
if (zero || match) {
memo[i + 1] = true;
}
return memo[i + 1];
}
if (isFirstMatching && helper(s, p, i - 1, j - 1, memo)) {
memo[i + 1] = true;
}
return memo[i + 1];
}
解法三：动态规划
有了上面两种方法和解释作为铺垫，我想迭代式的动态规划应该不难理解。这里我们不再用递归，而是使用 for 循环的形式，先上代码：
public boolean isMatch(String s, String p) {
if (s.equals(p)) {
return true;
}
char[] sArr = s.toCharArray();
char[] pArr = p.toCharArray();
boolean[][] dp = new boolean[sArr.length + 1][pArr.length + 1];
dp[0][0] = true;
for (int i = 1; i <= pArr.length; ++i) {
dp[0][i] = pArr[i - 1] == '*' ? dp[0][i - 2
