class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        bool dp[m+1][n+1];
        //initialisation
        dp[0][0] = true;
        for(int i=1;i<=m;i++){
            dp[i][0] = false;
        }
        for(int j=1;j<=n;j++){
            if(p[j-1] == '*'){
                dp[0][j] = dp[0][j-1];
            }else{
                dp[0][j] = false;
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //condition 1 
                if((s[i-1] == p[j-1]) || (p[j-1] == '?')){
                    dp[i][j] = dp[i-1][j-1];
                }
                //condition 2
                else if(p[j-1] == '*'){
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
                else{
				// condition 3 if chars doesn't matches
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
};