class Solution {

public:
bool isMatch(string s, string p) {
    int dp[1010][1010];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int j=1;j<=p.size();j++){
        if (p[j-1] == '*'){
            dp[0][j] = 1;
        }
    }
    for(int i = 1;i<=s.size();i++){
        for(int j=1;j<=p.size();j++){
            if (p[j-1] == '*'  ){ //&& j >1
                dp[i][j] = dp[i][j-2] ||  dp[i-1][j] && (p[j-2] == s[i-1] || p[j-2]=='.' );
            }
            else{
                dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1]=='.');
            }
        }
    }
    if (dp[s.size()][p.size()] == 1) return true;
    else return false;
}

};