dfs 正则表达式

class Solution:
    """
    @param s: A string 
    @param p: A string includes "?" and "*"
    @return: is Match?
    """
    def isMatch(self, s, p):
        # write your code here
        self.cache = {}
        return self.helper(s, p, s_at=len(s)-1, p_at=len(p)-1)
        
        
    def helper(self, s, p, s_at, p_at):
        if (s_at, p_at) in self.cache:
            return self.cache[(s_at, p_at)]
            
        if p_at < 0:
            return s_at < 0
        
        if s_at < 0:
            for i in range(0, p_at+1):
                if p[i] != "*":
                    return False
            return True
        
        if p[p_at] == ‘?‘:
            is_match = self.helper(s, p, s_at-1, p_at-1)
        elif p[p_at] == ‘*‘:
            is_match = self.helper(s, p, s_at-1, p_at) or                     self.helper(s, p, s_at, p_at-1) 
        else:
            is_match = s_at >= 0 and s[s_at]==p[p_at] and                    self.helper(s, p, s_at-1, p_at-1)
        self.cache[(s_at, p_at)] = is_match
        return is_match