LeetCode_10_RegularExpressionMatching
题目分析：
以 s="aaa" p = "ab*a*c*a"为例
a b * a * c * a
T F F F F F F F F
a F T F T F T F T F
a F F F F T T F T T
a F F F F F T F T T
和上题一样 '.'和相配的情况依旧，看*的情况，只是*的使用方式多了一层分类。
1.p.charAt(j - 1) != '*'
dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
2.p.charAt(j - 1) == '*' 分类
这里有个和上一题的本质区别，*的分类取决于*前面的值，所以多一层分类。
2.1如果 p[j - 2]和s[i - 1]不能配上 s:"b" p:"a*"这种情况
也就是 s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.'
那么只能配0个 dp[i][j] = dp[i][j - 2];
2.2如果配得上那么 s:"a" p:"a*"这种情况
2.2.1 0个 dp[i][j - 2] s="a" p="aa*"
2.2.2 1个 dp[i][j - 1] s="aa" p="aa*"
2.2.3 多个 dp[i - 1][j] s="aaa" p="aa*"
dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
解法一：
public static boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean dp[][] = new boolean[m + 1][n + 1];
dp[0][0] = true;
/**
* 初始项 默认了输入数据不可能以*开头！
* s ""
* p "a*"
* 这种情况看初始项 如果为*那么*前可以为0个 所以对应的dp[i][j - 2]位置如果可配 那么一定可配
*/
for (int i = 1; i <= p.length(); i++) {
if(p.charAt(i - 1) == '*')
dp[0][i] = dp[0][i - 2];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if(p.charAt(j - 1) == '*'){
/**
* 是* 那么 *当0个还是多个
*/
if(s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.'){
/**
* s "b"
* p "a*"
* 上一个值不等
* 只能当0个
*/
dp[i][j] = dp[i][j - 2];
}else {
/**
* 上一个相等
* 可能当0或多个
* s "a"
* p "a*"
* 0个 dp[i][j - 2] s="a" p="aa*"
* 1个 dp[i][j - 1] s="aa" p="aa*"
* 多个 dp[i - 1][j] s="aaa" p="aa*"
*/
dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
}
}else {
dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
}
}
}
return dp[m][n];
}
解法二：
public static boolean isMatch(String s, String p) {
/**
* p是空 那么是有s是空能配上
*/
if (p.isEmpty()) return s.isEmpty();
/**
* p(1)是* 与否 直接迭代 反正都递归了 也就将上方的循环写成了递归
* 本质还是 等于*时 将*前一个数 从0次开始 依次使用
*/
if (p.length() > 1 && p.charAt(1) == '*') {
/**
* 左方是用0次 右方是+1次
* isMatch2(s.substring(1, s.length()), p) 这个写法 s配了一个 p不变
* 是+1次的成型所在
*/
return isMatch(s, p.substring(2, p.length())) || (! s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1, s.length()), p));
} else {
return !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1, s.length()), p.substring(1, p.length()));
}
}