弱鸡进城纪实。
今天遇到的一道正则表达式匹配问题的题，题目大意是这样的：
给定两个字符串s和p，其中s是匹配串，p是模式串，p中定义了两个匹配符：
‘.’：通配符，可以指代任何字符（不含’*’）。
‘*‘：该字符前的一个字符可能出现任意次，该字符包括’.’，出现次数可能为零。
问题当然就是判定给定的s与p是否匹配了。
OK，说实话，我一开始连这个问题都没看明白，后来翻别人的解法之后才明白过来……英文不好真是……哎……
这个问题的最难点就在于‘*’的处理。’*’前面的字符可能在匹配串中出现0次1次2次……这么多情况该怎么去处理？这些情况都有可能成功匹配，该怎么去简洁的处理这个问题？
递归。
递归最适合的就是处理这种需要退回栈的问题，从几个基本问题出发，在递归中不断地对分支进行处理。那么具体到这道题，有些什么基本情况呢？
模式串p的第二个字符不是’*‘，那么只需要考察模式串和匹配串第一个字符是否相同，若相同，则递归的处理从下一个字符开始的s和p。
模式串p的第二个字符是’*‘，那么对于’*‘前的字符i，对于每个可能的匹配次数进行匹配后再依次进行递归。
整个思路很清晰，也很有效率。下面附上代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public boolean isMatch(String s, String p) { //模式串p是空字符串时，只需要考察匹配串s是不是也为空。 if (p.length() == 0) return s.length() == 0; //模式串p的长度为1，或者第二个字符不是'*'时，只需要考察模式串的第一个字符和匹配串的第一个字符是否相同。 if (p.length() == 1 || p.charAt(1) != '*') { //如果此时匹配串已为空或者p和s的第一个字符不相同，则返回错误。 if (s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0))) return false; //否则考察从下一个字符开始的s和p是否匹配。 return isMatch(s.substring(1), p.substring(1)); } else { //此时模式串的第二个字符是'*'，这种情况下，我们假定'*'前的字符为i，并且匹配串s中，前k个字符是i（k可能为零，模式串中的i可能是通配符） //按照规则，i可能会匹配匹配串s中从第一个字符起的0到k个i，那么，对于这k种情况，我们应该分别递归的调用这个函数进行考察。 int len = s.length(); int i = -1; while (i < len && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) { if (isMatch(s.substring(i + 1), p.substring(2))) return true; i++; } //当所有过程被执行完毕还是没有返回true时，两个字符串不匹配。 return false; } }