剑指offer第二版-19.正则表达式匹配

本系列导航：剑指offer（第二版）java实现导航帖

面试题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