动规训练四：Leetcode 10. 正则表达式
题目描述
给你一个字符串 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
提示：
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
题解
这道题有一定难度，题解写了好几个小时，感觉不大好讲，不过我们 还是按照我们说的动态规划三部曲来，没看过的看我之前写的文章：告别动态规划，谈谈我的一些经验
一、定义数组的含义
字符串问题，90% 可以用动态规划来解决，对于这种有两个字符串的，基本都是二维数组来存放，我们定义 dp[i] [j] 的含义是当字符串 s 的长度为 i，模式串 p 的长度为 j 时，两者是否匹配，那么 dp[len_s] [len_p] 就是我们要的答案了。
注：len_s 表示字符串 s 的长度，len_p 表示 p 的长度。
二、找出数组元素之间的关系式
在比较字符的过程中，由于 p[j] 有三种类型的字符：.，*和普通字符，分以下情况讨论
1、当 p[j] 为 “.” 或者普通字符：这种情况比较简单，直接与 s[i] 进行匹配：
1） 如果匹配成功，那么就继续往下匹配，则有 dp[i] [j] = dp[i-1] [j-1]
2）如果匹配不成功，则有 dp[i] [j] = false。
2、如果 p[j] 为 * 时，稍微复杂一些，这里我们假设 p[j] 前面的一个字符是 b，即
p[j-1] = 'b';p[j] = '*'; // 主要是为了方便讲解
分如下情况讨论
（1）因为 * 可以代表 0 个或多个前面的字符，所以我们必须要考虑他前面的元素 p[j-1]。因为 * 是跟着他前一个字符走，前一个能匹配上 s[i]，* 才能有用，前一个都不能匹配上 s[i]，* 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符，这里相当于把 p[j] 和 [j-1] 两个字符b*都被删除了，那么有 dp[i] [j] = dp[i] [j – 2]。
也就是说，当 p[j-1] != s[i] 时，有 dp[i] [j] = dp[i] [j – 2]。
（2） 另一种就是当 p[j-1] = = s[i] 时，那么还会有如下三种情况：
1). 当 * 匹配 0 个字符时：其实和上面情况类似，相当于 p[j] 和 [j-1] 两个字符b*都被删除了，那么有 dp[i] [j] = dp[i] [j – 2]。，
2). 当 * 匹配 1 个时：如果只匹配了一个，即 p[j] 和 [j-1] 两个字符b* 变成了一个字符 b，这是相当于把 p[i] = * 这个字符删除了，那么有 dp[i] [j] = dp[i] [j-1]。
3). 当 * 匹配多个时：匹配多个时，相当于把 b* 变成了 bb*、bbb*等等，由于 b 是和 s[i] 匹配的，那我们可以拿 b 和 s[i] 相互抵消掉，然后 b* 还是保持原来的模样，和 s 后面的字符继续匹配，相当于把 s[i] 这个字符删除了，原理类似，这时有 dp[i] [j] = dp[i-1] [j]。
所以当 p[j-1] = = s[i] 时，有如下情况：
dp[i][j] = dp[i][j-2] // 匹配 0 个的情况
dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
dp[i][j] = dp[i-1][j] // 多个字符匹配的情况
即
dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
三、找出数组初始值
初始值还是比较容易找的，当两个字符串都是空字符串时，有 dp[0] [0] = true。
当 s 是空字符，p 不是空字符串时，我们需要判断 p[j] 是否为 *，如果为 *，则 dp[0] [j] = dp[0] [j – 2]。
当 s 不是空字符，p 是空字符串时，则有 dp[i][0] = false。
看代码吧，代码有详细解释
public boolean isMatch1(String s, String p){
if(s == null || p == null)
return false;
int len_s = s.length();
int len_p = p.length();
//存放状态，默认初始值都是 false。
boolean[][]dp = new boolean[len_s+1][len_p+1];
//初始化
dp[0][0] = true;
for(int j = 1; j <= len_p; j++){
if(p.charAt(j-1) == '*')
dp[0][j] = dp[0][j-2];
}
for(int i = 1; i <= len_s; i++){
for(int j = 1; j <= len_p; j++){
//如果不为‘*’且匹配
if(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1))
dp[i][j] = dp[i-1][j-1];
//如果是 *
else if(p.charAt(j-1)=='*'){
//如果p[j]前面的字符p[j-1]与s[i]字符不匹配，则匹配0个
if(j!=1&&p.charAt(j-2)!='.'&&p.charAt(j-2)!=s.charAt(i-1)){
dp[i][j] = dp[i][j-2];
}else{
//否则有三种情况：
//匹配0个，匹配1个，匹配多个
dp[i][j] = dp[i][j-2] || dp[i][j-1]||dp[i-1][j];
}
}
}
}
return dp[len_s][len_p];
}