剑指 Offer 19. 正则表达式匹配

classSolution {
    public booleanisMatch(String s, String p) {
        int m =s.length();
        int n =p.length();
        int i = 0,j = 0;
        char[] s1 =s.toCharArray();
        char[] p1 =p.toCharArray();
        returnisMatch(s1,p1,m,n,i,j);
    }

    private boolean isMatch(char[] s1, char[] p1, int m, int n, int i, intj) {
        if(i == m && j == n) return true;
        if(i<m && j<n) {
            if(s1[i] == p1[j] || p1[j] == '.'){
                if(j+1<n && p1[j+1] == '*'){
                    return isMatch(s1, p1, m, n, i, j + 2)||isMatch(s1, p1, m, n, i + 1, j)||isMatch(s1, p1, m, n, i + 1, j + 2);
                }else{
                    return isMatch(s1, p1, m, n, i + 1, j + 1);
                }
            } else if (j + 1 < n && p1[j + 1] == '*') {
                return isMatch(s1, p1, m, n, i, j + 2);
            } }
        while(j<n){
            if(p1[j] == '*') j++;
            else if(j+1<n && p1[j+1] == '*'){
                j = j+2;
            }else{
                return false;
            }
        }
        return i == m && j ==n;
    }
}

public booleanisMatch(String s, String p) {
        int m =s.length();
        int n =p.length();
        int i = m-1,j = n-1;
        char[] s1 =s.toCharArray();
        char[] p1 =p.toCharArray();
        returnisMatch(s1,p1,i,j);
    }

    private boolean isMatch(char[] s1, char[] p1,int i, intj) {
        if(i == -1 && j == -1) return true;
        if(i>=0 && j>=0) {
            if(s1[i] == p1[j] || p1[j] == '.'){
                return isMatch(s1, p1,i - 1, j - 1);
                
            } else if (p1[j] == '*') {
                if(j>0 && p1[j-1] == s1[i] || p1[j-1] == '.'){
                    return isMatch(s1, p1,i - 1, j - 1) || isMatch(s1, p1,i - 1, j) || isMatch(s1, p1,i, j - 2);
                }
                return isMatch(s1, p1,i, j - 2);
            }
        }
        while(j>=0){
            if(j>0 && p1[j] == '*'){
                j = j - 2;
            } else{
                return false;
            }
        }
        return i == -1 && j == -1;
    }