/*
1. 状态定义:  f[i][j] 表示  s[1~j] 和 p[1~i] 匹配, 并且p[i]结尾
2. 状态计算: 将集合按 p[i] 结尾划分:
    p[i] == '.'  f[i][j] = f[i-1][j-1]
    p[i] == ~    f[i][j] = f[i-1]f[j-1] && s[j] == p[i]
    p[i] == '*'  ?* 作为空:   f[i][j] == f[i-2][j]
                 ?* single?: f[i][j] == f[i-1][j] && p[i-1] == s[j-1] 
                 ?* mutil?:  f[i][j] == f[i][j-1] && p[i-1] == s[j-1] && p[i-1] == s[j]
3. 边界:  f[~][~] = false; f[0][0] = true;
4. 遍历要从 0~j, 因为可能有空串  !!!
5. testcase :
""
".*"

*/

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

        f[0][0] = true;
        for (int i = 1 ; i <= n ; i++){
            char pc = p.charAt(i-1);
            for(int j = 0; j <= m; j++){
                if ( j >= 1 && euqal( pc, s.charAt(j-1)) ) {
                    f[i][j] = i >= 1 && j >= 1 && f[i-1][j-1];
                } else if(pc == '*'){
                    f[i][j] = j >=2 && i >=2 && f[i][j-1] && euqal(p.charAt(i-2), s.charAt(j-2)) && euqal(p.charAt(i-2), s.charAt(j-1));
                    f[i][j] = f[i][j] || (i >= 2 && f[i-2][j]);
                    f[i][j] = f[i][j] || (i >= 1 && f[i-1][j] && euqal(p.charAt(i-2), s.charAt(j-1)));
                }
            }
        }
        return f[n][m];
    }
    boolean euqal(char a, char b){
        return a == b || a == '.' || b =='.';
    }
}