手写正则表达式匹配

题目

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

搜索-穷举所有可能匹配

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        return solve(str,pattern,0,0);
    }
    
    private boolean solve(char[] str,char[] pattern,int i,int j){
        // 写出递归要终止的条件
        if(i==str.length){ //要匹配模式的字符串完了已经
            if(j == pattern.length)// 模式串完了
                return true;
            else{ // 模式串没完
                if(isEnd(pattern,j)){ //后面可以出现0次扩展
                    return true;
                }else{ // 模式串没完，后面出现了必须要匹配的
                     return false;
                }
            }
        }
        
        if(j+1 < pattern.length && pattern[j+1]=='*'){ //遇到了"*"
            if(judge(str[i],pattern[j])){
                return solve(str,pattern,i,j+2) || solve(str,pattern,i+1,j);
            }else{
                return solve(str,pattern,i,j+2);
            }
        }else{  //没遇到"*"
            if(j < pattern.length && judge(str[i],pattern[j])){ //单个字符匹配上了
                return solve(str,pattern,i+1,j+1);
            }else{
                return false;
            }
        }
    }
    
    private boolean isEnd(char[] pattern,int end){ // 判断是否是 a*b*c*的格式
        if((pattern.length - end) % 2 == 1){
            return false;
        }
        for(int offset = 1; end + offset < pattern.length ; offset += 2){
            if(pattern[end + offset] != '*')
                return false;
        } 
        return true;
    }
    
    private boolean judge(char a, char b){
        if(a == b || b == '.'){
            return true;
        }else{
            return false;
        }
    }
}