这道题首先要把题目读懂，不然会因为想当然而制造了很多错误的解法。在isMatch()这个方法里，要求前者s与p模式匹配，而不是s是p的子集或者相反。另外，关于星号的定义也与真正的正则不太相同。这里的星号”*“是要匹配星号前面的字符，有零个或者多个。因此，根据题目可以假设模式中如果出现星号，则星号之前必然有字符，而不会出现诸如”**“这样的字符。
因此，我们可以稍微改变一下匹配字符p的形状。在没有星号的字符后面认为添加一个不存在的字符（比如”#”号），使得这个匹配字符工整，方便后续操作。
这样的转换下，如下字符则会变成下列的样子，把新生成的字符叫做pp：
a -> a#
aa -> a#a#
a*a -> a*a#
因此制作如下两个辅助私有方法：
// 判断当前字符是否是多重匹配
private boolean isMultiple(int i, String pp) {
return pp.charAt(i + 1) == '*';
}
// 判断当前字符是否是通配符
private boolean isAnySingle(int i, String pp) {
return pp.charAt(i) == '.';
}
基本思路解法是利用动态规划，创建一个二维数组dp[][]。拿s = "aab"和p = "c*a*b"来举例，制作好的二维数组如下所示：
| a | a | b | |
| c* | |||
| a* | |||
| b# |
只需要把这个表格填满就得到了结果。先填写第一列：
boolean hasSingleBefore = false;
for (int j = 0; j < pp.length() / 2; j++) {
if (j == 0) {
if (isAnySingle(j, pp) || pp.charAt(j) == s.charAt(0)) {
dp[0][j] = true;
} else {
dp[0][j] = false;
}
} else {
if (isMultiple(j * 2, pp)) {
if (dp[0][j - 1]) {
dp[0][j] = true;
} else if (hasSingleBefore) {
dp[0][j] = false;
} else if (pp.charAt(j * 2) == s.charAt(0) || isAnySingle(j * 2, pp)) {
dp[0][j] = true;
} else {
dp[0][j] = false;
}
} else {
if (hasSingleBefore) {
dp[0][j] = false;
} else if (pp.charAt(j * 2) == s.charAt(0) || isAnySingle(j * 2, pp)) {
dp[0][j] = true;
} else {
dp[0][j] = false;
}
}
}
if (!isMultiple(j * 2, pp)) hasSingleBefore = true;
}
这是一段极为复杂的代码，需要考虑很多情况。前几行首先填写dp[0][0]的值。接下来判断当前匹配字符的情况：
- 是多重匹配字符
这种情况下，如果上一个匹配为true的话，那么意味着匹配字符如果新添加任何字符，这里都应该为true。比如”xxx”和”xxx”模式匹配成功，那么匹配字符新添加一多重匹配字符不影响匹配结果，因为新添加的字符可以为零或者多个。
如果上一个是为false的话，说明之前的字符匹配失败，但并不代表当前字符匹配也失败。因为”a”和”b“匹配失败，但是如果匹配字符加上一个”a“则匹配成功。因此这里使用一个hasSingleBefore来记录先前的匹配记录中是否曾存在过单一匹配字符的匹配情况。如果有的话则当前字符匹配继续失败。
如果没有的话还要看原字符和当前匹配字符是否相同，或者匹配字符是否为通配符，如果两者任一为真，则当前匹配也为true，反之则假。
- 是单一匹配字符
若当前匹配字符为单一匹配字符的情况（后面接”#”），则检查以前匹配中是否出现过单一匹配，如果出现过则当前为false。为什么呢？拿”a”和”a#”来举例，因为单一匹配曾出现过，所以匹配字符再添加任何单一字符的话，原字符并没有新的字符来应对，因此必然为false。
如果没出现过的话，同样检查字符是否相同或者通配符，是为真，反之为假。
结果如下：
| a | a | b | |
| c* | false | ||
| a* | true | ||
| b# | false |
获取完第一列之后，按顺序填入每一行。每个值根据不同情况会依赖于自己左上方的三个值。这里又分为多种情况来讨论。注意这里循环的外层使用pp.length() / 2来限制，是因为处理后的pp字符串为原来的扩展长度。在使用循环计数器j的时候，需要乘以2，才能转换成pp中的字符。
for (int j = 0; j < pp.length() / 2; j++) {
for (int i = 1; i < s.length(); i++) {
if (isMultiple(j * 2, pp)) {
if (j - 1 >= 0 && dp[i][j - 1]) {
dp[i][j] = true;
} else if (dp[i - 1][j]) {
if (isAnySingle(j * 2, pp) || pp.charAt(j * 2) == s.charAt(i)) {
dp[i][j] = true;
} else {
dp[i][j] = false;
}
} else {
dp[i][j] = false;
}
} else {
if (isAnySingle(j * 2, pp) || pp.charAt(j * 2) == s.charAt(i)) {
if ((j - 1 >= 0 && dp[i - 1][j - 1])) {
dp[i][j] = true;
} else if (dp[i - 1][j]) {
dp[i][j] = false;
} else {
dp[i][j] = false;
}
} else {
dp[i][j] = false;
}
}
}
}
- 当前为多重匹配字符
这个值跟DP表格中左上方三个值的真假都相关。如果上方的值为真，那么该值为真。为什么？考虑一个s字符”a”和匹配字符”a*“，如果匹配字符添加任何一个多重匹配值，二者应该继续保持匹配状态，因为多重匹配可以为零。
如果上方的值为假，但是左侧的值为真，则要看当前字符和匹配字符是否相同，或者匹配字符是否为通配符。
- 为单一匹配字符
与上面差不多。
其实里面的逻辑有些冗余，代码有待继续整理优化。但是考虑到做了这题已经花了我一整天，能够通过已经很不容易，索性使用这个原本记录我的思考的算法，而不是精简优化。