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

import time
from typing import List
class Solution:
    cache = {}
    count = 0
    def isMatch2(self, s: str, p: str) -> bool:
        i = 0
        j = 0
        k = -1        
        if len(p) == 0 and len(s) == 0:
            return True
        if len(p) == 0:
            return False
        if len(s) == 0:
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True
            return False
        if p[0] != s[0] and p[0] != '?' and p[0] != '*':                
            return False
        if p[-1] != s[-1] and p[-1] != '?' and p[-1] != '*':                
            return False                    
        p_tmp = p.replace("*", "")
        if len(p_tmp) > len(s):
            return False
        while i < len(s) and j < len(p):
            if i < k:
                i += 1
                continue
            k = -1
            if p[j] != '?' and p[j] != "*":
                if s[i] != p[j]:
                    return False
                else:
                    j += 1
                    i += 1
                    continue
            if p[j] == '?':
                j += 1
                i += 1
                continue
            # handle for '*'
            if p[j] == '*':                
                next_token = p[j]
                while (next_token == '*') and j < len(p)-1:
                    j = j+1                
                    next_token = p[j]
                if next_token != '*':                    
                    for m in range(len(s)-1, i-1, -1):
                        if s[m] == next_token or next_token == '?':                            
                            if self.isMatch(s[m:], p[j:]):
                                return True
                            else:
                                continue
                else:
                    return True
                continue
        if j == len(p) and i == len(s):
            return True
        if i == len(s) and j < len(p):
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True            
        return False
    
    def isSStarMatch(self, s: str, p: str) -> bool:
        i = 0
        j = 0
        k = -1        
        if len(p) == 0 and len(s) == 0:
            return True
        if len(p) == 0:
            return False
        if len(s) == 0:
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True
            return False
        if p[0] != s[0] and p[0] != '?' and p[0] != '*':                
            return False
        if p[-1] != s[-1] and p[-1] != '?' and p[-1] != '*':                
            return False
        p_tmp = p.replace("*", "")
        if len(p_tmp) > len(s):
            return False
                
        while i < len(s) and j < len(p):
            if i < k:
                i += 1
                continue
            k = -1
            if p[j] != '?' and p[j] != "*":
                if s[i] != p[j]:
                    return False
                else:
                    j += 1
                    i += 1
                    continue
            if p[j] == '?':
                j += 1
                i += 1
                continue
            # handle for '*'
            if p[j] == '*':                
                next_token = p[j]
                while (next_token == '*') and j < len(p)-1:
                    j = j+1                
                    next_token = p[j]
                if next_token != '*':                    
                    # print(f"{s[i:]}, {p[j:]}")
                    # s[i:].rfind(p[j:]) == len(s[i:]) - len(p[j:])
                    s_tmp = s[i:]
                    p_tmp = p[j:]
                    n = -1
                    np = 0
                    if len(s_tmp) < len(p_tmp):
                        return False
                    for m in range(len(s_tmp)-1, -1, -1):
                        if np == len(p_tmp):
                            return True
                        if s_tmp[m] != p_tmp[n] and p_tmp[n] != '?':                                                        
                            return False
                        n -= 1
                        np += 1
                    return True
                else:
                    return True
                continue
        if j == len(p) and i == len(s):
            return True
        if i == len(s) and j < len(p):
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True
        return False    
    
    def isNormalMatch(self, s: str, p: str) -> bool:
        i = 0
        j = 0
        k = -1        
        if len(p) == 0 and len(s) == 0:
            return True
        if len(p) == 0:
            return False
        if len(s) == 0:
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True
            return False
        if p[0] != s[0] and p[0] != '?' and p[0] != '*':                
            return False
        if p[-1] != s[-1] and p[-1] != '?' and p[-1] != '*':                
            return False
        if len(p) != len(s):
            return False        
        c_key = f"{s}!{p}!0"
        if c_key in self.cache:
            return self.cache[c_key]        
        while i < len(s) and j < len(p):
            if i < k:
                i += 1
                continue
            k = -1
            if p[j] != '?' and p[j] != "*":
                if s[i] != p[j]:
                    self.cache[c_key] = False
                    return False
                else:
                    j += 1
                    i += 1
                    continue
            if p[j] == '?':
                j += 1
                i += 1
                continue
            # handle for '*'
            if p[j] == '*':                
                next_token = p[j]
                while (next_token == '*') and j < len(p)-1:
                    j = j+1                
                    next_token = p[j]
                if next_token != '*':                                
                    for m in range(len(s)-1, i-1, -1):
                        if s[m] == next_token or next_token == '?':                            
                            if self.isNormalMatch(s[m:], p[j:]):
                                self.cache[c_key] = True
                                return True
                            else:
                                continue
                else:
                    self.cache[c_key] = True
                    return True
                continue
        if j == len(p) and i == len(s):
            self.cache[c_key] = True
            return True
        if i == len(s) and j < len(p):
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                self.cache[c_key] = True
                return True
        self.cache[c_key] = False
        return False
    
    def isStarMatch(self, s: str, p_star: List[str]) -> bool:
        i = 0
        j = 0
        k = -1        
        if len(p_star) == 0 and len(s) > 0:
            return False
        if len(p_star) == 0 and len(s) == 0:
            return True
        if len(p_star) == 1:
            p = p_star[0]
            c_key = f"{s}!{p}!{len(p_star)}"
            if c_key in self.cache:
                return self.cache[c_key]
            res = self.isSStarMatch(s, p)
            self.cache[c_key] = res
            return res
        c_key = f'{s}!{p_star}!{len(p_star)}'
        if c_key in self.cache:
            # print(f"{s}, {p_star}, {len(p_star)}, cached: {self.cache[c_key]}")
            # self.count += 1
            return self.cache[c_key]        
        p_tmp = ''.join(p_star)
        p_tmp = p_tmp.replace('*', '')
        if len(p_tmp) > len(s):
            self.cache[c_key] = False
            return False        
        # print(f'{len(s)}, {len(p_star)}')
        half = int(len(p_star)/2)
        p_star_left = p_star[:half]
        p_tmp = ''.join(p_star_left)
        p_tmp = p_tmp.replace('*', '')
        n_left = len(p_tmp)
        p_star_right = p_star[half:]
        p_tmp = ''.join(p_star_right)
        p_tmp = p_tmp.replace('*', '')
        n_right = len(p_tmp)
        total_sn = len(s)
        for i in range(n_left-1, total_sn):
            sn_left = i+1
            sn_right = total_sn-sn_left
            if sn_right < n_right:
                self.cache[c_key] = False
                return False
            c_t = p_star_left[-1][-1]
            if s[i] != c_t and c_t != '?' and c_t != '*':
                continue
            if len(p_star_left[-1]) > 1 and i>=1:
                c_t = p_star_left[-1][-2]
                if s[i-1] != c_t and c_t != '?' and c_t != '*':
                    continue
            c_t = p_star_right[-1][-1]
            if s[-1] != c_t and c_t != '?' and c_t != '*':
                continue
            s_left = s[:sn_left]
            s_right = s[sn_left:]            
            if self.isStarMatch(s_left, p_star_left) and self.isStarMatch(s_right, p_star_right):
                self.cache[c_key] = True
                return True
        self.cache[c_key] = False
        return False
    
    def isMatch(self, s: str, p: str) -> bool:        
        i = 0
        j = 0
        k = -1        
        if len(p) == 0 and len(s) == 0:
            return True
        if len(p) == 0:
            return False
        if len(s) == 0:
            next_token = p[j]            
            while (next_token == '*') and j < len(p)-1:
                j = j+1                
                next_token = p[j]                    
            if next_token == '*':
                return True
            return False
        if p[0] != s[0] and p[0] != '?' and p[0] != '*':                
            return False
        if p[-1] != s[-1] and p[-1] != '?' and p[-1] != '*':                
            return False                    
        p_tmp = p.replace("*", "")
        if len(p_tmp) > len(s):
            return False
        
        index = p.find("*")        
        if index == -1:
            return self.isNormalMatch(s, p)                        
        p_star = []
        p_tmp_single = p[:index]
        if p_tmp_single != '':            
            if not self.isNormalMatch(s[:len(p_tmp_single)], p_tmp_single):
                return False
            s = s[len(p_tmp_single):]
        p_tmp = p[index:]
        while index != -1:            
            j = 0
            next_token = p_tmp[j]            
            while (next_token == '*') and j < len(p_tmp)-1:
                j = j+1                
                next_token = p_tmp[j]                    
            if j == len(p_tmp)-1:                                
                p_star.append(p_tmp)
                break
            p_tmp_2 = p_tmp[j:]
            index = p_tmp_2.find("*")
            if index != -1:                
                p_tmp = p_tmp[:j+index]            
            p_star.append(p_tmp)
            p_tmp = p_tmp_2[index:]
        return self.isStarMatch(s, p_star)


38646