模拟正则表达式匹配

2/22/2017来源:ASP.NET技巧人气:2953

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

递归模拟,当pattern数组中下一个为'*',则递归枚举是匹配到原串的哪个位置

public class Solution {
    PRivate char[] str ;
    private char[] pattern  ;
    public boolean match(char[] str, char[] pattern)
    {
        this.str = str  ;
        this.pattern = pattern ;
        return match(0 , 0) ;
    }
    private boolean judge(int sPos , int pPos){
        int i = pattern.length-1  ;
        while(i >= pPos){
            if(pattern[i] == '*' || (i+1 < pattern.length && pattern[i+1] == '*')){
                i-- ;
            }else{
                return false ;
            }
        }
        return true;
    }
    private boolean match(int sPos , int pPos){
        if(sPos == str.length){
            return judge(sPos , pPos) ;
        }
        while(sPos < str.length && pPos < pattern.length){
            if(pattern[pPos] == '*'){
                int ne = pPos+1 ;
                while(ne < pattern.length && pattern[ne] == '*')
                    ne++ ;
                if(pattern[pPos-1] == '.'){
                    for(int i = sPos;i <= str.length;i++){
                        if(match(i,ne))return true ;
                    }
                    return false ;
                }
                if(match(sPos , ne))return true ;
                for(int i = sPos;i < str.length && str[i] == pattern[pPos-1];i++){
                    if(match(i+1 , ne)){
                        return true ;
                    }
                }
                return false ;
            }else if(pPos+1 < pattern.length && pattern[pPos+1] == '*'){
                pPos++ ;
            }else if(pattern[pPos] == '.'){
                sPos++;
                pPos++ ;
            }else if(str[sPos] == pattern[pPos]){
                sPos++ ;
                pPos++ ;
            }else{
                return false ;
            }
        }
        if(pPos == pattern.length){
            if(sPos < str.length)return false ;
            else return true ;
        }
        return judge(sPos , pPos) ;
    }
}