正则表达式匹配
- '.' 匹配任意单个字符。
- '*' 匹配零个或多个前面的元素。
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
- 输入: s = "aa", p = "a"
- 输出: false
- 解释: "a" 无法匹配 "aa" 整个字符串。
- 输入: s = "aa", p = "a*"
- 输出: true
- 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
- 输入: s = "ab", p = ".*"
- 输出: true
- 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
- 输入: s = "aab", p = "c*a*b"
- 输出: true
- 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
- 输入: s = "mississippi", p = "mis*is*p*."
- 输出: false
解析
这应该是遇到的第一个困难类型的题目了。如果只有 '.' 这个字符，匹配是十分简单的，每匹配一个字符，问题就转化为在剩余的字符串中做相同的操作，例如对于字符串 s="aa", p=".a" 而言，因为第一个字符 'a' 和 '.' 相匹配，所以问题就转化成 s="a", p= "a" 是否匹配。如果我们用函数 f(x, y) 表示字符串 s 的 前 x 位与字符串 p 的前 y 位是否匹配，那么它具有以下的表达式：
如果 s.charAt(x)可以匹配p.charAt(y)，则 f(x, y) = f(x+1, y+1)
否则，f(x, y) = false
然而，因为 '*' 定义为可以匹配零个或多个前面的元素，这使得上述规则不再适用，所以我们要对它进行适当的修正。首先，'*' 必须在某个小写字母或者 '.' 之后，这就意味着我们必须校验一个字符后边是否有 '*' 标记，如果有，字符串 s 可以与这部分不匹配，例如 s="aa", p="b*aa"，虽然第一个字符 'a' 不能匹配 'b'，但由于 '*' 的原因，可以忽略这部分不同。所以我们有了如下策略：
记 canMatchFirst表示s.charAt(x)是否可以匹配p.charAt(y)
如果p.charAt(y+1)=='\*'，f(x, y) = f(x, y+2) || (canMatchFirst && f(x+1, y))
否则和只有 '.' 时一样，f(x, y) = canMatchFirst && f(x+1, y+1)
有了思路，我们就可以写代码了，参考如下：
public boolean isMatch(String s, String p) {
return isMatch(s, p, s.length(), p.length(), 0, 0);
}
private boolean isMatch(String s, String p, int lenOfS, int lenOfP, int startS, int startP) {
// 当前参与递归运算的长度
int currLenOfS = lenOfS - startS;
int currLenOfP = lenOfP - startP;
if (currLenOfP == 0) {
return currLenOfS == 0;
}
char pc = p.charAt(startP);
// 第一个字符是否匹配
boolean canMatchFirst = currLenOfS != 0 && (pc == '.' || s.charAt(startS) == pc);
// 第二个字符是 * 的情况
if (currLenOfP > 1 && p.charAt(startP + 1) == '*') {
return isMatch(s, p, lenOfS, lenOfP, startS, startP + 2)
|| (canMatchFirst) && isMatch(s, p, lenOfS, lenOfP, startS + 1, startP);
} else {
return (canMatchFirst) && isMatch(s, p, lenOfS, lenOfP, startS + 1, startP + 1);
}
}
总结
虽然我们经常使用正则表达式，但是它的实现确实是十分复杂的，以上只能当做一个引子，展示了正则表达式最简单的几个情况，但是它却为我们了解正则表达式的实现提供了思路。以上的分析思路也十分重要，在之后的很多问题中，我们都需要这样思考。好了，接下来让我们看一个有趣的题目吧。
下题预告
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。</div>
* 输入: [1,8,6,2,5,4,8,3,7]
* 输出: 49
相关源码请加QQ获取。
【感谢您能看完，如果能够帮到您，麻烦点个赞~】
更多经验技术欢迎前来共同学习交流：一点课堂-为梦想而奋斗的在线学习平台 http://www.yidiankt.com/
![关注公众号，回复“1”免费领取-【java核心知识点】]
QQ讨论群：616683098
QQ：3184402434
想要深入学习的同学们可以加我QQ一起学习讨论~还有全套资源分享，经验探讨，等你哦!