模拟正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含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) ;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!