<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:
    int ssize;
    int psize;
    bool sol;
    vector<bool> visited;
    bool isMatch(string s, string p) {
        
        ssize = s.size();
        psize = p.size();
        if (psize == 0 || ssize == 0) visited = vector<bool>(1);
        else visited = vector<bool>(psize * ssize);
        vector<int> v(psize);
        vector<char> c(psize);
        int count = 0;
        char firstNon = '.';
        for (int i = psize-1; i >= 0; i--){
            v[i] = count;
            c[i] = firstNon;
            if (p[i] != '*') {
                count++;
                firstNon = p[i];
            }
            
        }
        match(s,p,0,0,v,c);
        return sol;
    }
    void match(string& s, string& p, int loc1, int loc2,vector<int>& v,vector<char>& c){
        int hash = psize * loc1 + loc2;
        if (sol || visited[hash]) return;
        visited[hash] = true;
        if (p[loc2] == '*'){
            int countNonAst = v[loc2];
            char firstNon = c[loc2];
           
            if (countNonAst > ssize - loc1) return;
            if (countNonAst == 0 || firstNon == '.') {sol = true; return;}
            for (int i = loc1; i < ssize - countNonAst + 1; i++){
                if (s[i] == firstNon || firstNon == '?') {
                    match(s,p,i,loc2+1,v,c);
                    if (sol) return;
                }

            }

        }
        else if (p[loc2] == s[loc1] || p[loc2] == '?'){
            if (loc2 == psize-1){
                if (loc1 == ssize-1){
                    sol = true;
                    return;
                }
            }
            else if (loc1 + 1 < ssize){
                match(s,p,loc1+1,loc2+1,v,c);
            }
            else{
                loc2++;
                while (loc2 < psize) if (p[loc2++] != '*') return;
                sol = true;
            }
            
        }
      
    }
};
12899