<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 solve(string& s, string& p, int i, int j, vector<vector<bool>>& dp) {
    //     if (i == s.size() && j == p.size())
    //         return true;
    //     if (j == p.size())
    //         return false;
    //     if (i == s.size()) {
    //         while (j < p.size() && p[j] == '*') {
    //             j++;
    //         }
    //         return j == p.size();
    //     }
    //     if (dp[i][j] != false) {
    //         return dp[i][j];
    //     }
    //     int ans = false;
    //     if (s[i] == p[j] || p[j] == '?') {
    //         ans = solve(s, p, i + 1, j + 1, dp);
    //     }
    //     if (p[j] == '*') {
    //         ans = solve(s, p, i + 1, j, dp) || solve(s, p, i, j + 1, dp);
    //     }
    //     dp[i][j] = ans;
    //     return dp[i][j];
    // }
    // bool solveByTabulation(string s, string p) {
    //     int n1 = s.size(), n2 = p.size();
    //     // create a 2-D vector
    //     vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
    //     // Initialize the base cases
    //     dp[n1][n2] = true; // Both strings are fully matched
    //     // if n1 < n2
    //     // Initialize the last row (when `s` is empty)
    //     for (int i = n2 - 1; i >= 0; i--) {
    //         if (p[i] == '*') {
    //             // * MADE A MISTAKE*
    //             dp[n1][i] = dp[n1][i + 1];
    //         } else {
    //             dp[n1][i] = false;
    //         }
    //     }
    //     for (int i = n1 - 1; i >= 0; i--) {
    //         for (int j = n2 - 1; j >= 0; j--) {
    //             if (s[i] == p[j] || p[j] == '?') {
    //                 dp[i][j] = dp[i + 1][j + 1];
    //             } else if (p[j] == '*') {
    //                 dp[i][j] = dp[i + 1][j] || dp[i][j + 1];
    //             } else {
    //                 dp[i][j] = false;
    //             }
    //         }
    //     }
    //     return dp[0][0];
    // }

    // bool solveBySpaceOpt(string s, string p) {
    //     int n1 = s.size(), n2 = p.size();
    //     // Create a 1-D vector
    //     vector<bool> prev(n2 + 1, false);
    //     vector<bool> curr(n2 + 1, false);

    //     // Initialize the base case
    //     prev[n2] = true; // Both strings are fully matched

    //     // Initialize the last row (when `s` is empty)
    //     for (int j = n2 - 1; j >= 0; j--) {
    //         if (p[j] == '*') {
    //             prev[j] = prev[j + 1];
    //         } else {
    //             prev[j] = false;
    //         }
    //     }

    //     // Fill the dp table row by row
    //     for (int i = n1 - 1; i >= 0; i--) {
    //         curr[n2] =
    //             false; // If `p` is empty but `s` is not, it's not a match
    //         for (int j = n2 - 1; j >= 0; j--) {
    //             if (s[i] == p[j] || p[j] == '?') {
    //                 curr[j] = prev[j + 1];
    //             } else if (p[j] == '*') {
    //                 curr[j] = prev[j] || curr[j + 1];
    //             } else {
    //                 curr[j] = false;
    //             }
    //         }
    //         // Move current row to previous row for the next iteration
    //         prev = curr;
    //     }

    //     return prev[0];
    // }
    // bool solveByColumnFillUsing1D(string s, string p) {
    //     int n1 = s.size(), n2 = p.size();
    //     // Create a 1-D vector to store the current column values
    //     vector<bool> dp(n1 + 1, false);

    //     // Initialize the base case
    //     dp[n1] = true; // Both strings are fully matched

    //     // Iterate over the pattern from right to left (column by column)
    //     for (int j = n2 - 1; j >= 0; j--) {
    //         bool prev =
    //             dp[n1]; // Store the value of dp[i + 1][j + 1] for the first
    //             row
    //         dp[n1] = (p[j] == '*' && dp[n1]); // Handle the base case for the
    //                                           // last row (empty string)

    //         for (int i = n1 - 1; i >= 0; i--) {
    //             bool temp = dp[i]; // Store the current value of dp[i][j + 1]
    //                                // before updating it

    //             if (p[j] == '*') {
    //                 dp[i] =
    //                     dp[i] ||
    //                     dp[i + 1]; // dp[i][j] = dp[i + 1][j] || dp[i][j + 1]
    //             } else {
    //                 dp[i] = (s[i] == p[j] || p[j] == '?') &&
    //                         prev; // dp[i][j] = dp[i + 1][j + 1]
    //             }

    //             prev = temp; // Update prev for the next iteration
    //         }
    //     }

    //     return dp[0];
    // }
    // bool solveBySpaceOpt(string s, string p) {
    //     int n1 = s.size(), n2 = p.size();
    //     // creating two 1-D vector
    //     vector<int> prev(n1 + 1, false);
    //     vector<int> curr(n1 + 1, false);
    //     //  MISTAKE
    //     if (n1 == 0 && n2 == 0) {
    //         return true;
    //     }
    //     // Initialize the base cases
    //     prev[n1] = true; // Both strings are fully matched
    //     for (int i = n2 - 1; i >= 0; i--) {
    //         // Initialize the base case for the current row
    //         curr[n1] = (p[i] == '*') && prev[n1];
    //         for (int j = n1 - 1; j >= 0; j--) {
    //             if (s[j] == p[i] || p[i] == '?') {
    //                 curr[j] = prev[j + 1];
    //             } else if (p[i] == '*') {
    //                 curr[j] = prev[j] || curr[j + 1];
    //             } else {
    //                 curr[j] = false;
    //             }
    //         }
    //         // shifting variable
    //         prev = curr;
    //     }
    //     return curr[0];
    // }
    // bool solveBySpaceOpt2(string s, string p) {
    //     int n1 = s.size(), n2 = p.size();
    //     vector<bool> arr(n1 + 1, false); // create  a 1-D vector
    //     arr[n1] = true;                  // dp[n1][n2] = true
    //     for (int i = n2 - 1; i >= 0; i--) {
    //         bool diagonal = arr[n1]; // diagonal --> dp[i+1][j+1]
    //         arr[n1] = (p[i] == '*') && arr[n1];
    //         for (int j = n1 - 1; j >= 0; j--) {
    //             bool diagonalUp = arr[j]; // dp[i][j+1] --> daigonalUp
    //             if (s[j] == p[i] || p[i] == '?') {
    //                 arr[j] = diagonal; // dp[i][j] = dp[i+1][j+1]
    //             } else if (p[i] == '*') {
    //                 arr[j] = arr[j] || arr[j + 1];
    //                 // dp[i][j] = dp[i][j+1] || dp[i+1][j]
    //             } else {
    //                 arr[j] = false;
    //             }
    //             // update store --> move up
    //             diagonal = diagonalUp; // dp[i+1][j+1] = dp[i][j+1]
    //         }
    //     }
    //     return arr[0];
    // }
    bool solveByTabulation(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        vector<vector<bool>> dp(n1 + 2, vector<bool>(n2 + 1, false));

        // Initialize the base case: both strings fully matched
        dp[n1][n2] = true;

        // Fill the DP table
        for (int i = n1 ; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                if (s[i] == p[j] || p[j] == '?') {
                    dp[i][j] = dp[i + 1][j + 1];
                } 
                else if (p[j] == '*') {
                    dp[i][j] = dp[i + 1][j] || dp[i][j + 1];
                } 
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[0][0];
    }
    bool isMatch(string s, string p) {
        // ector<vector<bool>> dp(s.size() + 1,
        //  vector<bool>(p.size() + 1, false));
        return solveByTabulation(s, p);
    }
};
17343