//f[i][j]表示s的前i个能否被p的前j个匹配。
//转移若s[i]==p[j]则f[i][j]=f[i-1][j-1]. 否则若p[j]=.也可以匹配，若=*则再判断p[j-1]与s[i]的关系
class Solution {
public:
    bool isMatch(string s, string p) {
        s = " "+s;  p = " "+p;                          //s,p可能为空
        int n = s.size(), m = p.size();
        bool f[n+1][m+1];
        memset(f,false,(n+1)*(m+1));
        f[0][0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i-1]==p[j-1] || p[j-1]=='.'){
                    f[i][j] = f[i-1][j-1];
                }
                else if(p[j-1]=='*'){
                    if(p[j-2]!=s[i-1] && p[j-2]!='.'){//*找前一个，前一个匹配不上，再往前找
                        f[i][j] = f[i][j-2];
                    }else{  //匹配上了
                        f[i][j] = (f[i-1][j] || f[i][j-1] || f[i][j-2]);//多个字符,单个字符,没有匹配
                    }
                }
            }
        }
        return f[n][m];
    }
};