/*
1. 状态定义: f[i][j] 为s[1...i] 和 p[1..j] 能完全匹配, 并且以p[j] 结尾
2. 状态计算: 按p[j]的不同划分为几种情况:
    2.1 p[j] == a-z -> f[i-1][j-1] && s[i] == p[j]
    2.2 p[j] == ?   -> f[i-1][j-1]
    2.3 p[j] == *   ->  当*为empty  : f[i][j-1]
                        当*为single : f[i-1][j-1]
                        当*为multi  : 应该是f[i-2][j], 而不是f[i-2][j-1], 因为*已经匹配多个了, 不用care * 前面的了
3. 边界: f[0][0] == true , 空串
4. s要从0开始扫描, 匹配空串

*/

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] f = new boolean[n+1][m+1];
        f[0][0] = true;

        for (int i = 0; i <= n ; i ++){
            char si = i == 0 ? ' ' : s.charAt(i-1);
            for (int j = 1 ; j <= m; j++){
                char pj = p.charAt(j-1);
                if (pj == '?'){
                    if (i >= 1) f[i][j] = f[i-1][j-1];
                } else if (pj == '*'){
                    f[i][j] = f[i][j-1];
                    if (i >= 1)   f[i][j] = f[i][j] || f[i-1][j-1] ;
                    if (i >= 2) f[i][j] = f[i][j] || f[i-2][j];
                } else {
                    if (i >= 1) f[i][j] = f[i-1][j-1] && si == pj;
                }
            }
        }
        return f[n][m];
    }
}