问题：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
官方难度：
Hard
翻译：
实现正则表达式匹配字符串，支持特殊符号“.”和“*”。
“.”匹配任意单个字符串。
“*”匹配0至人任意多个“*”之前的字符串。
算法必须满足任意的正则表达式匹配。
例子：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("aab", ".*a") → false
isMatch("aab", ".*ab") → true
- 每次我都将入参检查这一步放到最后，只是提醒一下，而这次却要在一开始就提起这一点。原因很简单：正则表达式匹配算法，是一定会使用递归的，在递归算法中，执行入参检查是一件非常不智的事情，因为在递归进入方法时，是一定符合入参规范的，多余的检查会影响效率。这时候合适的做法有2个：在进入方法前检查入参；或者将递归方法独立出来。这里选择第二种做法。
- 基本的思想是：从头开始，消去将匹配成功的部分，不断循环直到字符串的长度为0。循环期间，只要出现不匹配的情况，直接返回false；或是在字符串还有剩余的情况下，正则表达式长度为0，返回false。
- 在进入循环之前，思考一个问题：有没有什么情况，可以不进入循环，直接判断匹配失败？实际上，在只有“.”和“*”的正则表达式，仅有“*”这个特殊符号会影响正则表达式匹配的长度。这样一来，可以从后往前遍历，直到在正则表达式中遇到“*”，只要出现不匹配，整个算法不匹配。
- 从前向后遍历，只有当第二个字符是“*”的时候，考虑特殊情况，否则单个字符匹配。
- 第二个字符是“*”，基本的思想是返回一个“*”匹配的长度。分2种情况：正常字符+“*”和“.*”。
- 先讨论“.*”的特殊情况。因为“.*”能匹配任意字符组合的任意长度字符串。这种情况下，讨论“*”匹配的长度是不现实的。这种时候就需要递归了。举一个简单的例子：“.*dd*”匹配“acdadd”，无法确定“.*”匹配的长度是2、4、5还是6。实际上“*”匹配长度是4或者6的时候，整个正则表达式都能匹配成功。此时，合理的做法是，考虑“.*”之后的正则表达式“dd*”，先判断这个正则表达式能否匹配空字符串，然后依次拿这个正则表达式去匹配“acdadd”、“cdadd”、……、“dd”、“d”。如果全都不匹配，那么整个不匹配。只要出现一个匹配，整个匹配。
- 然后考虑正常字符+“*”的情况，看似简单，但其实是比“.*”的思考更加复杂。
- 先考虑正则表达式长度为2的情况，即只有正常字符+“*”，直接返回“*”匹配的长度。
- 在考虑正则表达式长度为3的情况，“*”前面和后面的字符的匹配情况，以及字符串最后一个字符和“*”后面的字符的匹配情况（这种情况不匹配，直接整个不匹配），满足这2个条件，会使“*”的匹配长度-1（得到的匹配长度小于0时，做0处理）。如“a*.”中，“a”可以匹配“.”，匹配“a”和“aa”时，“a*”的匹配长度分别是0和1。
- 然后考虑正则表达式长度大于3的情况，根据第4个字符是否为“*”，又可以分2种情况。
- 第4个字符是“*”的情况下，根据第3个字符还可以分为3种情况。第一种情况，如“a*.*b”的匹配能力和“.*b”是等价的。“a*”的意义在于，尽可能消去字符串中开头的“a”的个数，从而减少之后“.*”的循环次数；第二种情况，如“a*a*b”，等价于“a*b”，消去一个“a*”进行递归；第三种情况，如“a*b*c”，这时要先考虑“b*”中第二个“*”的匹配情况。获取字符串中，第一个不是“a”的字符串，如果不是“b”，表明“b*”的匹配个数为0，消去“b*”递归。不然（包括原字符串全是“a”的情况），返回“a*”的匹配个数。
- 第4个字符不是“*”的情况下，根据第三个字符也能分为3种情况。
- 第一种情况，如“a*ba”，正常返回“a*”的匹配个数。
- 第二种情况，如“a*aab”，计算正则表达式“*”之后“a”的个数count，以及字符串“a”开头的个数length。根据正则表达式“a*”之后下一个不是“a”的字符，分3种情况。第一种，没有或不是“.”或不是“*”，返回“a*”的匹配长度；第二种，“.”，如“a*aaa.b”和“aaaacb”，消去count的值（count>length直接匹配失败），递归，等价于“a*.b”和“acb”的匹配；第三种，“*”，先将count-1，之后与第二种的操作基本相同。
- 最后一种情况：第3个字符是“.”且第4个字符不是“*”，如“a*.b..*”，但是由于第5个及之后的字符是不确定的（“*”和“.”），不能确定“a*”的具体匹配长度。与“.*”的处理类似，拿之后的正则表达式去匹配“a*”的所有可能性。如字符串为“aabcde”，依次拿“.*b..*”去匹配“aabcde”、“abcde”、“bcde”，期间只要出现一次匹配，整个匹配成功，否则整个匹配失败。
- 当字符串匹配完成，但是正则表达式还有剩余，检查剩余的正则表达式能否匹配空字符串。
解题代码：
public static boolean isMatch(String s, String p) {
// 递归方法不适用入参检查
if (s == null || p == null) {
throw new IllegalArgumentException("Input error");
}
// 循环匹配最后一位，若匹配失败，直接匹配失败
while (p.length() > 0 && s.length() > 0) {
if (p.substring(p.length() - 1).equals("*")) {
break;
} else {
if (singleMatch(s.charAt(s.length() - 1), p.charAt(p.length() - 1))) {
p = p.substring(0, p.length() - 1);
s = s.substring(0, s.length() - 1);
} else {
return false;
}
}
}
return isMatchTrue(s, p);
}
private static boolean isMatchTrue(String s, String p) {
// 待处理的正则
String pDeal;
// 消去的字符串长度
int sReduce;
// 以字符串为主体，匹配正则
while (s.length() > 0) {
// 正则长度为0
if (p.length() == 0) {
return false;
}
if (p.length() > 1 && p.charAt(1) == '*') {
// 第二个字符：*
pDeal = p.substring(0, 2);
sReduce = starMatch(s, p);
// 在内部方法中，已经通过递归得出结果
if (sReduce == -1) {
return true;
} else if (sReduce == -2) {
return false;
}
} else {
// 单字符匹配
pDeal = p.substring(0, 1);
if (!singleMatch(s.charAt(0), p.charAt(0))) {
return false;
}
sReduce = 1;
}
// 消去字符串
s = s.substring(sReduce);
p = p.substring(pDeal.length());
}
// 字符串解析完成，但正则还有剩余
if (!regularEqualsNull(p)) {
return false;
}
return true;
}
// 普通字符+*，返回*匹配的长度
private static int starMatchNormal(String s, String p) {
char pBeforeStar = p.charAt(0);
// 正则长度：2
if (p.length() == 2) {
return getLength(s, pBeforeStar);
}
char pAfterStar = p.charAt(2);
// 正则长度：3
if (p.length() == 3) {
int l = getLength(s, pBeforeStar);
// 字符串s的最后一个字符，会影响*匹配长度
if (singleMatch(s.charAt(s.length() - 1), pAfterStar)) {
if (singleMatch(pBeforeStar, pAfterStar)) {
l--;
}
} else {
// 最后一个字符不匹配，整体不匹配
return -2;
}
return l < 0 ? 0 : l;
}
// 正则第四个字符：*
if (p.charAt(3) == '*') {
// 如(aaabcd,a*.*d)
// a*是否存在，不影响整体的匹配结果
// 但是可以尽可能消去字符串s中，a起始的个数，减小.*匹配的负担
if (pAfterStar == '.') {
return getLength(s, pBeforeStar);
}
// 如a*a*，与a*等价
if (pAfterStar == pBeforeStar) {
return isMatchTrue(s, p.substring(2)) ? -1 : -2;
}
// 余下情况，如a*b*，考虑b*匹配长度
if (pAfterStar != notXFromStart(s, pBeforeStar)) {
// b*匹配长度：0
return isMatchTrue(s, p.substring(0, 2) + p.substring(4)) ? -1 : -2;
}
// b*匹配长度大于1；或字符串全部由a组成
return getLength(s, pBeforeStar);
} else {
// 如a*.
// 无法确定*匹配的具体长度
if (p.charAt(2) == '.') {
// a*之后，所有的正则
String pAfterPoint = p.substring(2);
// 匹配字符串中，*所有可能性
int posibility = getLength(s, pBeforeStar) + 1;
for (int i = 0; i < posibility; i++) {
if (isMatchTrue(s, pAfterPoint)) {
return -1;
}
if (s.length() == 0) {
return -2;
}
s = s.substring(1);
}
return -2;
}
// 如a*a
if (p.charAt(2) == pBeforeStar) {
// a*之后a的个数
int count = 1;
for (int i = 3; i < p.length(); i++) {
if (p.charAt(i) == pBeforeStar) {
count++;
} else {
break;
}
}
// 如a*aaaab的b
Character after = count == p.length() - 2 ? null : p.charAt(count + 2);
int l = getLength(s, pBeforeStar);
if (after == null || !(after.equals('.') || after.equals('*'))) {
// 类似a*aaab一定不匹配aab
if (count > l) {
return -2;
}
return l - count;
}
// 如(a*aaa.b,aaaacb)，count=3
if (after.equals('.')) {
if (count > l) {
return -2;
}
// 等价(a*.b,acb)
s = s.substring(count);
p = p.substring(0, 2) + p.substring(2 + count);
if (isMatchTrue(s, p)) {
return -1;
}
return -2;
}
// 如(a*aaa*b,aaaacb)，count=2
// 等价(a*b,aacb)
if (after.equals('*')) {
count--;
if (count > l) {
return -2;
}
s = s.substring(count);
p = p.substring(2 + count);
if (isMatchTrue(s, p)) {
return -1;
}
return -2;
}
}
// 余下情况，如a*ba
return getLength(s, pBeforeStar);
}
}
// 返回*匹配长度
private static int starMatch(String s, String p) {
if (p.charAt(0) == '.') {
// .*
p = p.substring(2);
// .*之后的正则，如果可以匹配空字符串，直接匹配成功
if (regularEqualsNull(p)) {
return -1;
}
// 用余下的正则，循环递归
for (int i = 0; i < s.length(); i++) {
String sAfter = s.substring(i);
if (isMatchTrue(sAfter, p)) {
return -1;
}
}
// 余下的都不成功，表示整个不匹配
return -2;
} else {
return starMatchNormal(s, p);
}
}
// 单个字符匹配
private static boolean singleMatch(char s, char p) {
if (p == '.' || p == s) {
return true;
}
return false;
}
// 一个可以表示为空字符串的正则表达式
private static boolean regularEqualsNull(String p) {
if (p.length() % 2 == 1) {
return false;
}
while (p.length() > 0) {
if (p.charAt(1) != '*') {
return false;
}
p = p.substring(2);
}
return true;
}
// 在字符串s中，第一个不是x的字符
private static char notXFromStart(String s, char x) {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != x) {
return s.charAt(i);
}
}
// s全部由x组成
return x;
}
// 字符串s中，以pBeforeStar开头的个数
private static int getLength(String s, char pBeforeStar) {
int l = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == pBeforeStar) {
l++;
} else {
break;
}
}
return l;
}
isMatch
相关链接：
https://leetcode.com/problems/regular-expression-matching/
PS：如有不正确或提高效率的方法，欢迎留言，谢谢！