<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: 

    def isMatch(self, s: str, p: str) -> bool:
        cache = {}
        def recurse(st,pt ,si,pi):
            # print(st,pt)
            if (si,pi) in cache:
                return cache[(si,pi)]
            if len(pt):
                tmp=st
                if pt[0] in ['?','*']:

                    if len(st):
                        st = st[1:]
                    else:
                        if pt[0] == '*':
                            if len(set(pt)) == 1:
                                return True
                        return False
                    if pt[0] == '?':
                        pt.pop(0)
                        b=recurse(st,pt , si+1,pi+1)
                        
                        cache[(si+1,pi+1)]=b
                        return b
                    else:
                        
                        b,c,d=recurse(tmp,pt[1:],si,pi+1) ,recurse(st,pt[1:],si+1,pi+1),recurse(st,pt,si+1,pi)
                        # if a:
                        #     cache[(tmp,tuple(pt))]=True
                        
                        cache[(si,pi+1)]=b
                        
                        cache[(si+1,pi+1)]=c
                        
                        cache[(si+1,pi)]=d
                        return max(b,c,d)

                else:
                    val=pt.pop(0)
                    if not st.startswith(val):
                        return False 
                    v=recurse(st[len(val):],pt,si+len(val),pi+1)
                    
                    cache[(si+len(val),pi+1)]=v
                    return v
            else:
                if len(st) == 0:
                    # print('aaaa')
                    return True
                else:
                    return False
        pattern = []
        tmp=''
        for x in p:
            if x in ['?','*']:
                if len(tmp):
                    pattern.append(tmp)
                    tmp=''
                pattern.append(x)
                
            else:
                tmp+=x
        if len(tmp):
            pattern.append(tmp)
        # print(s,pattern)
        return recurse(s,pattern,0,0)
        


        


        


        

        
        
56684