我的原文链接：http://ben-personal.top/2020/03/leetcode-10-regex/
本题要求实现一个简单的正则匹配，是动态规划的经典题型。在理解本题的过程中，可以形成动态规划的思维。本文将遵循我改进算法的思路，提供四种解题方法，在效率上逐渐提高。本文将通过Java实现，其他语言也很容易改写。
题目如下：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
链接：https://leetcode-cn.com/problems/regular-expression-matching
一、递归法
递归是最先能想到的思路。既然是字符串匹配，那匹配成功的部分就可以不再去管，转而对s和p的剩下部分进行匹配。递归程序的Java实现如下：
public boolean isMatch1(String s, String p) {
if(p.isEmpty())
return s.isEmpty();
boolean firstMatch = (!s.isEmpty()) &&
(p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
if (p.length() > 1 && p.charAt(1) == '*')
return firstMatch && isMatch1(s.substring(1), p) || isMatch1(s, p.substring(2));
else
return firstMatch && isMatch1(s.substring(1), p.substring(1));
}
二、改进的递归
在第一种方法中，需要对字符串不断切分，效率很低。不妨通过传递索引加以避免。因此有了递归的改进版本：
/**
* @param i: p子串的起点
* @param j: s子串的起点
* @return
*/
public boolean is_match2(int i, int j, String s, String p){
if(i == p.length())
return j == s.length();
boolean firstMatch = (j < s.length()) &&
(p.charAt(i) == s.charAt(j) || p.charAt(i) == '.');
if(p.length()-i > 1 && p.charAt(i+1) == '*')
return firstMatch && is_match2(i,j+1,s,p) || is_match2(i+2, j, s, p);
else
return firstMatch && is_match2(i+1, j+1, s, p);
}
public boolean isMatch2(String s, String p){
return is_match2(0, 0, s, p);
}
三、动态规划
方法二虽然解决了字符串切分的效率问题，但不难发现，仍存在重复计算的问题，因此可以通过动态规划，从后向前算，并将答案存储起来，避免重复的计算。
public boolean isMatch3(String s, String p){
//dp[i][j]存储s[i:]能否与p[j:]匹配
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
for (int i = p.length(); i >= 0; i--) {
for (int j = s.length(); j >= 0; j--) {
if(i == p.length())
{
dp[j][i] = j == s.length();
} else {
boolean firstMatch = (j < s.length()) &&
(p.charAt(i) == s.charAt(j) ||p.charAt(i) == '.');
if(p.charAt(i) == '*' && p.length()>i)
dp[j][i] = dp[j][i+1];
else if(p.length()-i > 1 && p.charAt(i+1) == '*')
dp[j][i] = firstMatch && dp[j+1][i] || dp[j][i+1];
else
dp[j][i] = firstMatch && dp[j+1][i+1];
}
}
}
这里要注意一点，当p子串以'*'开头时，要单独讨论一下，容易分析出来，这时等价于去掉'*'（这样才能保证后续的判断正确）。
if(p.charAt(i) == '*' && p.length()>i)
dp[j][i] = dp[j][i+1];
四、正向存储
方法三利用DP从后往前存储，避免重复计算，但实际上也有问题，有些子串的判断其实有多余。因为我们在做递归正向匹配的时候，很多子串并不需要进行匹配。
动态规划的思想其实很简单，不过就是将可能出现的重复特征提取出来，并存储起来。那何必拘泥于从后往前算呢？
因此方法四直接在方法二的基础上，加上一个数组用以存储已经算过的情况，每次递归时，判断一下是否算过即可：
boolean[][] flag;
boolean[][] dp;
/**
* @param i: p子串的起点
* @param j: s子串的起点
* @return
*/
public boolean is_match4(int i, int j, String s, String p){
if (flag[j][i]) {
return dp[j][i];
}
if(i == p.length()) {
dp[j][i] = j == s.length();
} else{
boolean firstMatch = (j < s.length()) &&
(p.charAt(i) == s.charAt(j) || p.charAt(i) == '.');
if(p.length()-i > 1 && p.charAt(i+1) == '*') {
dp[j][i] = firstMatch && is_match4(i,j+1,s,p) || is_match4(i+2, j, s, p);
} else {
dp[j][i] = firstMatch && is_match4(i+1, j+1, s, p);
}
}
flag[j][i] = true;
return dp[j][i];
}
//结合isMatch2和isMatch3的方法，
//需要什么值就算什么，并存储，效率最高
public boolean isMatch4(String s, String p){
dp = new boolean[s.length()+1][p.length()+1];
flag = new boolean[s.length()+1][p.length()+1];
return is_match4(0, 0, s, p);
}
抓住动态规划的思想：用存储的方式避免重复讨论，就不必拘于形式。
