题解 | #正则表达式匹配#动态规划解法

这里dp[row][col]的意思是，str的row长度去和pattern的col长度做一个正则匹配是否能成功，所以说此时最后一位字符分别是row-1和col-1位置

    public boolean match (String str, String pattern) {
        if(str==null||pattern==null) return false;
        if(!check(str)) return false;
        int rows = str.length();
        int cols = pattern.length();
        boolean[][] dp = new boolean[rows+1][cols+1];
        //str做行，pattern做列的行列对应模型
        dp[0][0] = true;
        for(int col = 1;col<=cols;col++){
            for(int row = 0;row<=rows;row++){
                //看结尾位置(注意是[row-1]和[col-1]字符)
                char pEnd = pattern.charAt(col-1);
                if(pEnd=='*'){
                    //1.*前的玩意一次都不出现
                    //2.*前的玩意p和sEnd匹配,如果p出现若干次能够使得dp[row-1][col]为true，那再多一次就好了
                    dp[row][col] = dp[row][col-2]||
                        (row>0&&isMatch(str.charAt(row-1),pattern.charAt(col-2))&&dp[row-1][col]);
                }else{
                    //如果不是*，那么只和左上角有关
                    dp[row][col] = row>0&&isMatch(str.charAt(row-1),pEnd)&&dp[row-1][col-1];
                }
            }
        }
        return dp[rows][cols];
    }
    public boolean isMatch(char s,char p){
        return s==p||p=='.';
    }
    public boolean check(String str){
        if("".equals(str)) return true;
        if(str.charAt(0)=='*') return false;
        for(int i = 1;i<str.length();i++){
            //两个*不能连着
            if(str.charAt(i)=='*'&&str.charAt(i-1)=='*'){
                return false;
            }
        }
        return true;
    }