class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size() + 1;
        int m = p.size() + 1;
        vector<vector<bool>> dp(n,vector<bool>(m,0));
        dp[0][0] = true;
        for(int j=2;j<m;j += 2)
        dp[0][j] = dp[0][j-2] && p[j-1] == '*';

        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                dp[i][j] = p[j-1] == '*' ?
                dp[i][j-2] || dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.') :
                dp[i-1][j-1] && (p[j-1] == '.' || s[i-1] == p[j-1]);
            }
        }

        return dp[n-1][m-1];
    }
};