递归-正则表达式匹配

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

示例1
输入
"aaa","a*a"
返回值
true

递归的解法

public class Solution {
    public boolean match(char[] str, char[] pattern) {
        if(str==null || pattern==null) return false; //判断参数存在，否则false
        return matchone(str,0,pattern,0);
    }
    public boolean matchone(char[] str,int s,char[] pattern,int p){
        if(s==str.length && p==pattern.length) return true;//二者均为空，为true
        if(s<str.length && p==pattern.length) return false;//非空匹配空，为flase
        //pattern后边至少有两个字符，且第二个为*
        if(p+1<pattern.length && pattern[p+1]=='*'){
            //当首字母匹配,可能有匹配一次或者多次的情况
            //当首字母不匹配，但是pattern为.时，可以看作首字母匹配，也可以看作首字母不匹配。此时结果需要加上匹配0次的可能
            if(s<str.length &&(pattern[p]==str[s]||pattern[p]=='.')){
                return matchone(str,s+1,pattern,p+2) || matchone(str,s+1,pattern,p)||matchone(str,s,pattern,p+2);
            }
            //首字母不匹配，也不是.,只有一种情况就是匹配了零次。
            else{
                return matchone(str,s,pattern,p+2);
            }
        }
        //假如后边不是*，则如果匹配或者为.,则后移以为，否则不匹配
        if(s<str.length &&(pattern[p]==str[s]||pattern[p]=='.')){
            return matchone(str,s+1,pattern,p+1);
        }
        return false;
    }
}

错误程序：通过实例：83.3%
问题理解的bug之一：ab可以匹配.*========不理解
从右向左一个一个匹配，逻辑不清晰

public class Solution {
    public boolean match(char[] str, char[] pattern){
        if(str.length==0){
            if(pattern.length==0){
                return true;
            }
            else{
                if(pattern.length>1){
                    for(int i=1;i<pattern.length;i+=2){
                        if(pattern[i]!='*'){
                            return false;
                        }
                    }
                    return true;
                }
                return false;
            }
        }
        if(pattern.length==0) return false;
        int right0 = str.length-1;
        int right1 = pattern.length - 1;
        while (right0 >=0 && right1>0) {
            if (str[right0] == pattern[right1] || pattern[right1] == '.') {
                if(right0>0){
                    right1--;
                    right0--;
                }
                else{
                    break;
                }
            }
            else {
                //System.out.println(right0 + "****" + right1);
                if (pattern[right1] == '*') {
                   while ((str[right0] == pattern[right1 - 1] || pattern[right1 - 1]=='.') &&right0>0) right0--;
                    if(right1-2>=0){
                        right1 -= 2;
                    }
                    else {
                        right1--;
                        break;
                    }
                }
                else{
                    break;
                }
            }
        }
        if ((str[right0] == pattern[right1] || pattern[right1]=='.')&& right0==0&& right1==0) return true;
        return false;
    }
}