本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題19：正則表達(dá)式匹配

題目要求：
實(shí)現(xiàn)正則表達(dá)式中.和*的功能旨别。.表示任意一個(gè)字符哄芜，*表示他前面的字符的任意次（含0次）。比如aaa與a.a和ab*ac*a匹配，但與aa.a和ab*a不匹配。

解題思路：
.就相當(dāng)于一個(gè)萬(wàn)能字符拿诸，正常匹配即可；但*的匹配會(huì)涉及到前一個(gè)字符塞茅。所以要分模式串后一個(gè)字符不是*或沒(méi)有后一個(gè)字符亩码，模式串后一個(gè)字符是*這幾個(gè)大的情況，之再考慮.的問(wèn)題野瘦。

package chapter3;
/**
 * Created by ryder on 2017/7/13.
 * 正則表達(dá)式匹配
 * 完成.(任何一個(gè)字符)和*(前面字符的任意次數(shù))
 */
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){
        //如果匹配串和模式串都匹配結(jié)束
        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;
        }
        //如果模式串的第二個(gè)字符不是*或者已經(jīng)只剩一個(gè)字符了
        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;
        }
        //如果模式串的第二個(gè)字符是*
        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
    }
}

運(yùn)行結(jié)果

true
true
false
false