难度 困难
请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次(含0次)。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
示例 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
一开始的思路，，，，好吧没有思路
只能使用字符串中关于正则的匹配API，代码如下
class Solution {
public boolean isMatch(String s, String p) {
return s.matches(p);
}
}
其实我们仔细考虑一下，无非就是分三种情况
假设主串为 A，模式串为 B , A 的长度为 n ，B 的长度为 m ，关注正则表达式 B 的最后一个字符是谁，它有三种可能，正常字符,* 和 .(点)，那针对这三种情况讨论即可，如下：
如果 B 的最后一个字符是正常字符，那就是看 A[n-1] 是否等于 B[m-1]，相等则看 A_{0..n-2}与 B_{0..m-2},不等则是不能匹配，这就是子问题。
如果 B 的最后一个字符是 .(点) ，它能匹配任意字符，直接看 A_{0..n-2}与 B_{0..m-2}
如果 B 的最后一个字符是 * ,它代表 B[m-2]=c 可以重复0次或多次，它们是一个整体 c*
情况一：A[n-1]是 0个 c，B 最后两个字符废了，能否匹配取决A_{0..n-1}和 B_{0..m-3}是否匹配
情况二：A[n-1]是多个 c 中的最后一个(这种情况必须 A[n−1]=c 或者 c=’.’)，所以 A 匹配完往前挪一个，B 继续匹配，因为可以匹配多个，继续看 A_{0..n-2}和 B_{0..m-1}是否匹配。
先来个某大神动态规划的思路
转移方程
f[i][j] 代表 A 的前 i 个和 B 的前 j 个能否匹配
对于前面两个情况，可以合并成一种情况 f[i][j] = f[i-1][j-1]
对于第三种情况，对于 c* 分为看和不看两种情况
不看：直接砍掉正则串的后面两个， f[i][j] = f[i][j-2]
看：正则串不动，主串前移一个，f[i][j] = f[i-1][j]
特判：需要考虑空串空正则
空串和空正则是匹配的，f[0][0] = true
空串和非空正则，不能直接定义 true 和 false ，必须要计算出来。(比如A=” “ ,B=abc*)
非空串和空正则必不匹配，f[1][0]=…=f[n][0]=false
非空串和非空正则，那肯定是需要计算的了。
大体上可以分为空正则和非空正则两种，空正则也是比较好处理的，对非空正则我们肯定需要计算，非空正则的三种情况，前面两种可以合并到一起讨论，第三种情况是单独一种，那么也就是分为当前位置是 * 和不是 * 两种情况了。
再来个递归代码,递归代码与上面的思路其实是一样的
package ddx.september.day29;
public class Normal_19 {
public boolean isMatch(String s, String p) {
if (s.length() == 0 ) {
//主串为空
if (p.length() % 2 != 0) {
//模式串长度为奇数，则一定不匹配，因为抵消不了奇数
//例如："." , "ab*","abc"
return false;
} else {
//长度为偶数，只需要判断偶数位上是不是*即可！
int i = 1;
while (i < p.length()) {
if (p.charAt(i) != '*') {
return false;
}
i += 2;
}
return true;
}
} else if (p.length() == 0) {
//模式串为空
return false;
} else {
char ch1 = s.charAt(0); //s的首位
char ch2 = p.charAt(0); //p的首位
char ch3 = 'a'; //p的下一位
if(p.length() > 1){
ch3 = p.charAt(1);
}
//照样分情况，看看是不是*
if(ch3 != '*'){
if(ch2 == ch1 || ch2 == '.'){
return isMatch(s.substring(1),p.substring(1));
}else{
//连正常字符和.都匹配不上
return false;
}
}else{
//难点就在于ch3是 *
//正常字符相等，或者是.
//即选择或者不选择！！！
//"aa"
//"a*a"
//上面两个字符串，碰到*可以选择，也可以不选择
if(ch2 == ch1 || ch2 == '.'){
//前者是选择，后者是不选择
return isMatch(s.substring(1),p) || isMatch(s,p.substring(2));
}else{
//连正常字符和.都匹配不上,那么ch2 和 ch3废了！！！！
return isMatch(s,p.substring(2));
}
}
}
}
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
