习惯github pages风格的请看我的另一篇博客
题目19：正则表达式匹配
请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。 匹配是指字符串的所有字符匹配整个模式。
举例说明
例如，字符串aaa与模式a.a和ab * ac * a匹配，但与aa.a和ab * a均不匹配
思路
递归实现
模式字符串pattern和待匹配字符串Str。匹配是指Str的所有字符匹配整个pattern。
- 每次从Str里拿出一个字符和pattern中的字符去匹配，主要的核心
- 1.下一个是不是*
- 2.str是否结束
- （3.当前字符是否匹配）
对每一个字符
-
- 一对多匹配：如果模式匹配字符的下一个字符
是*
- 1.1 str已经结束：
match(s, p+2) - 1.2 str没有结束：
- 1.2.1如果pttern当前字符和str的当前字符
匹配，：有以下三种可能情况
1）pttern当前字符能匹配 str 中的 0 个字符：match(s, p+2)
2）pttern当前字符能匹配 str 中的 1 个字符：match(s+1, p+2)
3）pttern当前字符能匹配 str 中的 多 个字符：match(s+1, p) - 1.2.2 如果pttern当前字符和和str的当前字符
不匹配
pttern当前字符能匹配 str 中的 0 个字符：match(s, p+2)
- 1.2.1如果pttern当前字符和str的当前字符
- 一对多匹配：如果模式匹配字符的下一个字符
-
- 一对一匹配 ：如果模式匹配字符的下一个字符
不是*
- 2.1 str已经结束：
return false; - 2.2 str没有结束：
- 2.1.1 匹配：
如果pattern中的字符ch是.或Str中的字符是ch，则对应位置匹配，在Str和pattern上都向后移动一个字符，也就是match(s+1, p+1) - 2.1.2 不匹配：
return false;
- 2.1.1 匹配：
- 一对一匹配 ：如果模式匹配字符的下一个字符
代码实现
public class _19 {
public static boolean match(String str, String pattern) {
if (str == null || pattern == null) {
return false;
}
return matchCore(str, 0, pattern, 0);
}
private static boolean matchCore(String str, int s, String pattern, int p) {
// str和pattern都到达尾，说明成功匹配
if (s >= str.length() && p >= pattern.length()) {
return true;
}
// 只有pattern到达结尾，说明匹配失败
if (s != str.length() && p >= pattern.length()) {
return false;
}
//pattern未结束，str有可能结束有可能未结束
// 1 --------------------------------------------
if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
if (s >= str.length()) {// 1.1 --------------------------------------------
return matchCore(str, s, pattern, p + 2);
}
// 1.2 --------------------------------------------
else {//1.2.1----------------------------------------
if (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '.') {
return
// 当前pattern匹配当前str 0个字符，如aa*a与aa
matchCore(str, s, pattern, p + 2)
// 当前pattern匹配当前str 1个字符，如ab*a与aba
|| matchCore(str, s + 1, pattern, p + 2)
//当前pattern匹配当前str 多个字符，如ab*a与aaba
|| matchCore(str, s + 1, pattern, p);
} else {//1.2.2 如a*与b-----------------------------
return matchCore(str, s, pattern, p + 2);
}
}
}
//2--------------------------------------
if (s >= str.length() ) {//2.1------------------------------
return false;
}
else {// 2.2----------------------------------
if (str.charAt(s) == pattern.charAt(p) || pattern.charAt(p) == '.') {
return matchCore(str, s + 1, pattern, p + 1);
}
}
return false;
}
public static void main(String[] args) {
System.out.println(match("aaa", "ab*ac*a"));//true
System.out.println(match("aaba", "ab*a*c*a"));//false
System.out.println(match("bbbba", ".*a*a"));//true
System.out.println(match("bcbbabab", ".*a*a"));//false
}
}
输出
image
