题解 | #通配符匹配,动态规划#

public class Solution {
    //"aab", "d*a*b"
    public boolean isMatch(String s, String p) {
        if(s == null || p == null || (s.length() > 0 && p.length() == 0)) return false ;        
        char[] arrs = s.toCharArray() ;
        char[] arrp = p.toCharArray() ;
        //f[i][j]表示s的前i个字符与p的前j个字符是否匹配
        boolean f[][] = new boolean[arrs.length + 1][arrp.length + 1] ;
        for(int i = 0 ; i <= arrs.length ; i ++) {
            for(int j = 0 ; j <= arrp.length ; j ++) {
                if(i == 0 && j == 0) {//初始化
                    f[i][j] = true ;continue ;
                }
                if(j == 0) {//初始化
                    f[i][j] = false ;continue ;
                }
                if(i == 0) {//初始化
                    if(j == 1) {
                        f[i][j] = arrp[j-1] == '*' ? true : false ;
                    } else {
                        f[i][j] = (arrp[j-1] == '*') && f[i][j-1] ;
                    }
                    continue ;
                }
                if(arrs[i-1] == arrp[j-1] || arrp[j-1] == '?') {//匹配一个字符
                    f[i][j] = f[i-1][j-1] ;
                } else {
                    if(arrp[j-1] == '*') {//* 匹配一个字符，匹配多个字符，匹配''
                        f[i][j] = f[i-1][j-1] || f[i-1][j] || f[i][j-1] ;
                    } else {//不匹配
                        f[i][j] = false ;
                    }
                }
            }
        }
        return f[arrs.length][arrp.length] ;
    }
}