面试题19：正则表达式匹配
题目要求：
实现正则表达式中.和*的功能。.表示任意一个字符，*表示他前面的字符的任意次（含0次）。比如aaa与a.a和ab*ac*a匹配，但与aa.a和ab*a不匹配。
解题思路：
.就相当于一个万能字符，正常匹配即可；但*的匹配会涉及到前一个字符。所以要分模式串后一个字符不是*或没有后一个字符，模式串后一个字符是*这几个大的情况，之再考虑.的问题。
package chapter3;
/**
* Created by ryder on 2017/7/13.
* 正则表达式匹配
* 完成.(任何一个字符)和*(前面字符的任意次数)
*/
public class P124_RegularExpressionsMatching {
public static boolean match(String str,String pattern){
if(str==null || pattern==null)
return false;
return matchCore(new StringBuilder(str),0,new StringBuilder(pattern),0);
}
public static boolean matchCore(StringBuilder str,Integer strIndex,StringBuilder pattern, Integer patternIndex){
//如果匹配串和模式串都匹配结束
if(strIndex==str.length() && patternIndex==pattern.length())
return true;
if(strIndex!=str.length() && patternIndex==pattern.length())
return false;
if(strIndex==str.length() && patternIndex!=pattern.length()) {
if(patternIndex+1<pattern.length()&&pattern.charAt(patternIndex+1)=='*')
return matchCore(str,strIndex,pattern,patternIndex+2);
else
return false;
}
//如果模式串的第二个字符不是*或者已经只剩一个字符了
if(patternIndex==pattern.length()-1|| pattern.charAt(patternIndex+1)!='*'){
if(pattern.charAt(patternIndex)=='.' || pattern.charAt(patternIndex)==str.charAt(strIndex))
return matchCore(str,strIndex+1,pattern,patternIndex+1);
else
return false;
}
//如果模式串的第二个字符是*
else{
if(pattern.charAt(patternIndex)=='.'||pattern.charAt(patternIndex)==str.charAt(strIndex))
return matchCore(str,strIndex+1,pattern,patternIndex)
||matchCore(str,strIndex+1,pattern,patternIndex+2)
||matchCore(str,strIndex,pattern,patternIndex+2);
else
return matchCore(str,strIndex,pattern,patternIndex+2);
}
}
public static void main(String[] args){
System.out.println(match("aaa","a.a"));//true
System.out.println(match("aaa","ab*ac*a"));//true
System.out.println(match("aaa","aa.a"));//false
System.out.println(match("aaa","ab*a"));//false
}
}
运行结果
true
true
false
false
