class Solution {
public:
    bool f[1002][1002];
    bool isMatch(string s, string p) {
        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=0;i<=s.size();i++){
            for(int j=1;j<=p.size();j++){
                if(p[j-1]!='*') f[i][j]= ((i>0)&&(p[j-1]=='.'||p[j-1]==s[i-1])&&f[i-1][j-1]);
                else{
                    f[i][j]=(f[i][j-2] || (i>0&&(p[j-2]=='.'||p[j-2]==s[i-1])&&f[i-1][j]));
                }
                //cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
            }
        }
        return f[s.size()][p.size()];

    }
};