class Solution {
    public boolean isMatch(String s, String p) {
        char[] chs = s.toCharArray();
        char[] chp = p.toCharArray();
        boolean[][] dp = new boolean[chs.length + 1][chp.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= chp.length && chp[i - 1] == '*'; i++)
            dp[0][i] = true;
        // dp[i][j] = dp[i-1][j-1], if chs[i-1] == chp[j-1] or chp[j-1] == '?'
        //          = dp[i-1][j] || dp[i][j-1], if chp[j-1] == '*'
        for (int i = 1; i <= chs.length; i++) {
            for (int j = 1; j <= chp.length; j++) {
                if (chp[j - 1] == '*')
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else if (chp[j - 1] == '?' || chs[i - 1] == chp[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
        return dp[chs.length][chp.length];
    }
}