<p>Given an input string (<code>s</code>) and a pattern (<code>p</code>), implement wildcard pattern matching with support for <code>&#39;?&#39;</code> and <code>&#39;*&#39;</code> where:</p>

<ul>
	<li><code>&#39;?&#39;</code> Matches any single character.</li>
	<li><code>&#39;*&#39;</code> Matches any sequence of characters (including the empty sequence).</li>
</ul>

<p>The matching should cover the <strong>entire</strong> input string (not partial).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> &quot;a&quot; does not match the entire string &quot;aa&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;&#39;*&#39; matches any sequence.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cb&quot;, p = &quot;?a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong>&nbsp;&#39;?&#39; matches &#39;c&#39;, but the second letter is &#39;a&#39;, which does not match &#39;b&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length, p.length &lt;= 2000</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
	<li><code>p</code> contains only lowercase English letters, <code>&#39;?&#39;</code> or <code>&#39;*&#39;</code>.</li>
</ul>

class Solution {
public:
// bool rec(int i, int j, string s, string p, vector<vector<int>> &dp) {
//     if(i==0 && j>0) {
//         //string is exhausted. Pattern must be all '*'s. 
//         for(int k=0; k<j; k++){
//             if(p[k]!='*') return false;
//         }
//         return true;
//     }

//     if(i==0 && j==0) {
//         //both exhausted. return true;
//         return true;
//     }

//     if(i>0 && j==0) {
//         //string is not exhausted but pattern is exhausted. thus this can't be matching. return false;
//         return false;
//     }


//     if(s[i-1]==p[j-1] or p[j-1]=='?') return dp[i][j] = rec(i-1, j-1, s, p, dp); //get it right? '?' can match with anything and if matching then matching.


//     //else if s[i]!=p[i] && p[i]!='?' thus p[i]=='*'
//     else if(p[j-1]=='*') {
//         return dp[i][j] = rec(i-1, j, s, p, dp) or rec(i, j-1, s, p, dp);
//     }

//     return dp[i][j] = false;


// //memoization is causing memory limit exceeded.

// }
int tab(string s, string t) {
    int n = s.size();
    int m = t.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    //1st base.
    dp[0][0] = true;
    //2nd base.
    for(int i=1; i<=n; i++){ 
        dp[i][0] = false;        
    }
    //3rd base.
    for(int i=1; i<=m; i++) {
        if(t[i-1]!='*') {
            //this isn't star hence this shall be false. Why? Why is mentioned in detail in notes:
            dp[0][i] = false;
        } else {
            //else it is star then it can be true. but only if all the elements before it are star. how to take than into account? we will use dp. else checking whole string would cause m^2 tle
            dp[0][i] = dp[0][i-1]; //what I had in mind was although dp[0][i] = true ^ dp[0][i-1]; //since it is true but only if the last one is true. but true^dp[0][i-1] = dp[0][i-1];
        }
    }
    //all bases are ready. make sure you don't tamper with other base cases.

    for(int i=1; i<=n; i++){ 
        for(int j=1; j<=m; j++){
            if(s[i-1]==t[j-1] or t[j-1]=='?') dp[i][j] = dp[i-1][j-1];
            else if(t[j-1]=='*') dp[i][j] = dp[i][j-1] or dp[i-1][j];
            else dp[i][j] = false;
        }
    }

    return dp[n][m];

}
int so(string s, string p) {
    int n = s.size();
    int m = p.size();
    vector<int> dp(m+1, 0);
    dp[0] = true;
    for(int i=1; i<=m; i++) {
        if(p[i-1]!='*') {
            //it depends on the earlier.
            dp[i] = false;
        } else {
            dp[i] = dp[i-1];//if it ain't '*' it can't match empty string. get it? we are checking the empty string on n= 0;
        }
    }

    for(int i=1; i<=n; i++){
        vector<int> curr(m+1, 0);
        curr[0] = false;
        for(int j=1; j<=m; j++){
            if(s[i-1]==p[j-1] or p[j-1]=='?') curr[j] = dp[j-1];
            else if(p[j-1]=='*') curr[j] = curr[j-1] or dp[j];
            else curr[j] = false;
        }
        dp = curr;
    }

    return dp[m];
}
    bool isMatch(string s, string p) {
        // int n = s.size();
        // int m = p.size();
        // vector<vector<int>> dp(n+1, vector<int>(m+1, -1));

        // return rec(n, m, s, p, dp);
        // return tab(s, p);
        return so(s, p);
    }
};
30081