暴力解法
在s串中，不能有和两个字符，
以上两种情况下，直接返回即可。
boolean process0(char[] s, char[] p, int si, int pi递归含义是：p字符串从pi出发一直到最后的字符，能否匹配出s这个字符串从si出发，一直到最后的字符串。
process0(s, p, 0, 0即可得到结果。
显然，当pi到结尾位置的时候，即：无匹配串的时候，si必须也要到结尾位置才能算匹配，否则不可能匹配上
if (pi == p.length {
return si == s.length;
}如果没有到结尾位置，说明:
pi还没到结尾
有效字符+'*'的模式，这样才能让有效字符被消化成空字符串。
// pi还没有到头
if (si == s.length {
// si已经到头了
if (((p.length - pi & 1 == 1 {
// pi及以后的字符必须首先是偶数个，剩余奇数个数了,后面如何都做不到变成空串了。
return false;
}
if (pi + 1 < p.length && p[pi + 1] == '*' {
// 后面必须是 : 有效字符 + "*"的组合模式
return process0(s, p, si, pi + 2;
}
return false;
}如果没有满足如上的条件，则说明：
si也没到头，pi也没到头
s[si] == p[pi] || p[pi] == '.'其次，s串从si+1一直到最后，也要可以被p串从pi+1到最后匹配上，逻辑如下：
// si和pi都没到头
if (pi == p.length - 1 || p[pi + 1] != '*' {
return (s[si] == p[pi] || p[pi] == '.' && process0(s, p, si + 1, pi + 1;
}如果也逃过了上述的判断，则说明：
pi 不是最后一个位置，且
// p[pi]和p[pi+1]先消解为空串，让si直接去匹配pi+2位置。
if (process0(s, p, si, pi + 2 {
return true;
}如果逃过了这步，说明消解为空串这条道路行不通，所以只能让： 匹配 ，然后将位置上的的衍生出：
1个
......
然后去匹配s串剩余的字符串。
for (int i = si; i < s.length; i++ {
if (p[pi] == s[i] || p[pi] == '.' {
// p[pi]匹配上了s[si]，然后将p[pi+1]位置上的的*衍生出n个p[pi]来进行匹配
// 只要匹配上了就直接返回true
if (process0(s, p, i + 1, pi + 2 {
return true;
}
} else {
// p[pi]未匹配上s[si],直接返回false
return false;
}
}完整代码如下：
public static boolean isMatch0(String s, String p {
if (s == null || p == null {
return false;
}
char[] str = s.toCharArray(;
char[] pStr = p.toCharArray(;
return isValid(str, pStr && process0(str, pStr, 0, 0;
}
// 首先过滤掉无效字符
private static boolean isValid(char[] str, char[] exp {
for (char c : str {
// str串中不能有.和*
if (c == '.' || c == '*' {
return false;
}
}
for (int i = 0; i < exp.length; i++ {
// *不能在exp的第一个位置
// 两个*不能连在一起
if (exp[i] == '*' && (i == 0 || exp[i - 1] == '*' {
return false;
}
}
return true;
}
private static boolean process0(char[] s, char[] p, int si, int pi {
if (pi == p.length {
return si == s.length;
}
// pi还没有到头
if (si == s.length {
// si已经到头了
if (((p.length - pi & 1 == 1 {
// pi及以后的字符必须首先是偶数个，剩余奇数个数了,后面如何都做不到变成空串了。
return false;
}
if (pi + 1 < p.length && p[pi + 1] == '*' {
// 后面必须是 : 有效字符 + "*"的组合模式
return process0(s, p, si, pi + 2;
}
return false;
}
// si和pi都没到头
if (pi == p.length - 1 || p[pi + 1] != '*' {
return (s[si] == p[pi] || p[pi] == '.' && process0(s, p, si + 1, pi + 1;
}
// pi 不是最后一个位置，且 p[pi+1] == '*'
// p[pi] 和 p[pi+1]至少可以先消解为空串，即p[pi]位置不做匹配
if (process0(s, p, si, pi + 2 {
return true;
}
// 如果走到这步，p[pi]消解为空串这条道路行不通
// 所以只能让：p[pi] 匹配 s[si]
// 然后将p[pi+1]的'*'衍生出:
// 0个p[pi]
// 1个p[pi]
// 2个p[pi]
// ...
// n个p[pi]
for (int i = si; i < s.length; i++ {
if (p[pi] == s[i] || p[pi] == '.' {
if (process0(s, p, i + 1, pi + 2 {
return true;
}
} else {
break;
}
}
return false;
}动态规划解法
暴力方法中，递归函数的可变参数有两个，而且是简单参数，所以可以改成二维动态规划，大家自行整理可能性和格子依赖关系，我自己整理了两遍，已晕：），完整代码为：
public static boolean isMatch2(String s, String p {
if (s == null || p == null {
return false;
}
char[] str = s.toCharArray(;
char[] pStr = p.toCharArray(;
if (!isValid(str, pStr {
return false;
}
boolean[][] dp = new boolean[str.length + 1][pStr.length + 1];
// 最后一列，除了 dp[str.length][pStr.length] = true
// 其余位置都是false
dp[str.length][pStr.length] = true;
// 最后一行
dp[str.length][pStr.length - 1] = false;
for (int i = pStr.length - 2; i >= 0; i-- {
if (((pStr.length - i & 1 == 1 {
dp[str.length][i] = false;
} else if (i + 1 < pStr.length && pStr[i + 1] == '*' {
dp[str.length][i] = dp[str.length][i + 2];
} else {
dp[str.length][i] = false;
}
}
// 倒数第二列
for (int i = str.length - 1; i >= 0; i-- {
dp[i][pStr.length - 1] = ((str[i] == pStr[pStr.length - 1] || pStr[pStr.length - 1] == '.' && dp[i + 1][pStr.length];
}
for (int i = str.length - 1; i>=0;i-- {
for (int j = pStr.length - 2; j >=0;j-- {
if (pStr[j+1]!='*' {
dp[i][j] = (str[i] == pStr[j] || pStr[j] == '.' && dp[i + 1][j + 1] ;
} else if (dp[i][j+2] {
dp[i][j] = true;
} else {
for (int k = i; k < str.length; k++ {
if (pStr[j] == str[k] || pStr[j] == '.' {
if (dp[k + 1][j+2] {
dp[i][j]= true;
break;
}
} else {
dp[i][j] = false;
break;
}
}
}
}
}
return dp[0][0];
}
// 首先过滤掉无效字符
private static boolean isValid(char[] str, char[] exp {
for (char c : str {
if (c == '.' || c == '*' {
return false;
}
}
for (int i = 0; i < exp.length; i++ {
if (exp[i] == '*' && (i == 0 || exp[i - 1] == '*' {
return false;
}
}
return true;
}枚举行为优化
通过动态规划解法，发现了一个可以优化的地方，如果可以省略动态规划解法中的下述循环，那算法效率就可以高很多，
for (int k = i; k < str.length; k++ {
if (pStr[j] == str[k] || pStr[j] == '.' {
if (dp[k + 1][j+2] {
dp[i][j]= true;
break;
}
} else {
// dp[i][j] = false;
break;
}
}通过分析可以得到，对于一个普遍位置（i，j），如上循环其实依赖关系是：
当初我们在求（i+1，j）的时候，我们依赖的位置是：
所以（i，j）位置可以由（i+1，j）和（i+1，j+2）推导出来，如上循环就简化了，优化后的代码如下：
public static boolean isMatch3(String s, String p {
if (s == null || p == null {
return false;
}
char[] str = s.toCharArray(;
char[] pStr = p.toCharArray(;
if (!isValid(str, pStr {
return false;
}
boolean[][] dp = new boolean[str.length + 1][pStr.length + 1];
// 最后一列，除了 dp[str.length][pStr.length] = true
// 其余位置都是false
dp[str.length][pStr.length] = true;
// 最后一行
dp[str.length][pStr.length - 1] = false;
for (int i = pStr.length - 2; i >= 0; i-- {
if (((pStr.length - i & 1 == 1 {
dp[str.length][i] = false;
} else if (i + 1 < pStr.length && pStr[i + 1] == '*' {
dp[str.length][i] = dp[str.length][i + 2];
} else {
dp[str.length][i] = false;
}
}
// 倒数第二列
for (int i = str.length - 1; i >= 0; i-- {
dp[i][pStr.length - 1] = ((str[i] == pStr[pStr.length - 1] || pStr[pStr.length - 1] == '.' && dp[i + 1][pStr.length];
}
for (int i = str.length - 1; i >= 0; i-- {
for (int j = pStr.length - 2; j >= 0; j-- {
if (pStr[j + 1] != '*' {
dp[i][j] = (str[i] == pStr[j] || pStr[j] == '.' && dp[i + 1][j + 1];
} else if (dp[i][j + 2] {
dp[i][j] = true;
} else if ((pStr[j] == str[i] || pStr[j] == '.' && (dp[i + 1][j + 2] || dp[i + 1][j] {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
// 首先过滤掉无效字符
private static boolean isValid(char[] str, char[] exp {
for (char c : str {
if (c == '.' || c == '*' {
return false;
}
}
for (int i = 0; i < exp.length; i++ {
if (exp[i] == '*' && (i == 0 || exp[i - 1] == '*' {
return false;
}
}
return true;
}