'''
keys: 
Solutions:
Similar: 10
T:
S:
'''
from typing import List



class Solution:

    # DP, O(S*P) for S and T, S and P as length of s and p
    # bottom up
    # https://leetcode.com/problems/wildcard-matching/discuss/370736/Detailed-Intuition-From-Brute-force-to-Bottom-up-DP
    def isMatch1(self, s: str, p: str) -> bool:
        s_len = len(s)
        p_len = len(p)
        
        # base cases
        if p == s or p == '*':
            return True
        if p == '' or s == '':
            return False
        
        # init all matrix except [0][0] element as False
        # rows for p and cols for s
        dp = [ [False] * (s_len + 1) for _ in range(p_len + 1)]
        
        for r in range(p_len+1):
            for c in range(s_len+1):
                cur_p, cur_s = r - 1, c-1
                if r == 0 and c == 0: # dp[0][0]
                    dp[r][c] = True
     
                elif r == 0: # no p
                    dp[r][c] = False
     				
                elif c == 0: # no s
                    dp[r][c] = p[cur_p] == '*' and dp[r-1][c]
     
                elif p[cur_p] == '*': # * as empty or * as one/more char(s)
                    dp[r][c] = dp[r-1][c] or dp[r][c-1]
                
                elif s[cur_s] == p[cur_p] or p[cur_p] == '?':
                    dp[r][c] = dp[r-1][c-1]
                
        return dp[p_len][s_len]
    
    
    
    # recursion with memo
    # O(min(S,P)) for the best case, and O(2^min(S,P/2)) for the worst case
    def isMatch(self, s: str, p: str) -> bool:
        p = self.remove_duplicate_stars(p)
        print (p)
        self.memo = {}
        return self.helper(s, p)
    
    
    def remove_duplicate_stars(self, p):
        if p == '': return p
        p1 = [p[0],]
        for x in p[1:]:
            # print (p1)
            if p1[-1] != '*' or p1[-1] == '*' and x != '*':
                p1.append(x)
        return ''.join(p1) 
    
    def helper(self, s, p):
        memo = self.memo
        if (s, p) in memo:
            return memo[(s, p)]
        
        if p == s or p == '*':
            memo[(s, p)] = True
        elif p == '' or s == '': # empty string
            memo[(s, p)] = False
        elif p[0] == s[0] or p[0] == '?': 
            memo[(s, p)] = self.helper(s[1:], p[1:])
        elif p[0] == '*': # match the empty string or one/more chars 
            memo[(s, p)] = self.helper(s, p[1:]) or self.helper(s[1:], p)
        else: memo[(s, p)] = False
        
        return memo[(s, p)]
        
