题解 | #通配符匹配#

输入是两个字符串，马上想到二维的动态规划，也就是行列对应模型，一个做行一个做列

	//'?' 可以匹配任何单个字符。
    //'*' 可以匹配任何字符序列（包括空序列）。
    public boolean isMatch(String s, String p) {
        if(s==p) return true;
        if(s==null||p==null) return false;
        if(s.length()==0&&p.length()==0) return true;
        if(s.length()==0){
            for(int i = 0;i<p.length();i++){
                if(p.charAt(i)!='*') return false;
            }
            return true;
        }
        if(p.length()==0){
            return false;
        }
        int rows = s.length()+1;
        int cols = p.length()+1;
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        //s做行，p做列的行列对应模型
        //注意末位字符要用row或者col  -1
        //第一行，s为0，p为col，当前位置如果p[col]不为*则为false,如果为*和p[col-1]有关
        boolean[][] dp = new boolean[rows][cols];
        dp[0][0] = true;
        for(int col = 1;col<cols;col++){
             dp[0][col] = pChars[col-1]=='*'&&dp[0][col-1];
        }
        //第一列:除了0 0为true，其他都是false,默认就是false
        //普通位置:1.末位相同，可以是同一个字符或者p那边是?，则和左上角有关
        //        2.p末位为*，只要是p[0][col-1]~p[row][col-1]有一个为true就为true，这里可以优化成
        //          dp[row][col-1]||dp[row-1][col]
        //        3.其他情况都是false
        for(int col = 1;col<cols;col++){
             for(int row = 1;row<rows;row++){
                 if(sChars[row-1]==pChars[col-1]||pChars[col-1]=='?'){
                     dp[row][col] = dp[row-1][col-1];
                 }else if(pChars[col-1]=='*'){
                     dp[row][col] = dp[row][col-1]||dp[row-1][col];
                 }
             }
         }
        
        return dp[rows-1][cols-1];
    }