<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:
    
    # dp[i,j] represents that s[i:] matches p[j:]
    
    star = "*"
    question_mark = "?"
    visited = {}
    dp = {}
    
    def isMatchRec(self, s: str, p: str, s_idx: int, p_idx: int) -> bool:
        if p_idx >= len(p) and s_idx >= len(s):
            return True
        
        #  matched all chars in p, but not in s
        if p_idx >= len(p) and s_idx < len(s):
            return False
        
        # last char in p is star
        if p_idx == len(p) - 1 and p[p_idx] == self.star:
            return True
        
        # matched all chars in s, but not in p
        if s_idx >= len(s):
            # print("Here!")
            # Check if all chars in p are *
            if p[p_idx:] == "*" * (len(p) - p_idx):
                return True
            else:
                return False
            
        if self.visited[s_idx][p_idx]:
            return self.dp[s_idx][p_idx]
        
        if p[p_idx] == self.star:
            # There are two options, 
            # Option 1: either match current char with *
            option_1 = self.isMatchRec(s, p, s_idx+1, p_idx)
            # Option 2: Match empty seq with *
            option_2 = self.isMatchRec(s, p, s_idx, p_idx + 1)
            self.dp[s_idx][p_idx] = option_1 or option_2
        elif p[p_idx] == self.question_mark:
            # Match current char with ?
            self.dp[s_idx][p_idx] = self.isMatchRec(s, p, s_idx+1, p_idx+1)
        else:
            if s[s_idx] == p[p_idx]:
                self.dp[s_idx][p_idx] = self.isMatchRec(s, p, s_idx+1, p_idx+1)
            else:
                self.dp[s_idx][p_idx] = False
                
        self.visited[s_idx][p_idx] = True
        return self.dp[s_idx][p_idx]
        
    
    def isMatch(self, s: str, p: str) -> bool:
        for s_idx in range(len(s)):
            self.visited[s_idx] = [False] * len(p)
            self.dp[s_idx] = [False] * len(p)
        return self.isMatchRec(s, p, 0, 0)
        
33235