[Python] super improve from 3000ms to 100ms by 4 lines


  • 0
    W

    class Solution(object):

    def __init__(self):
        self.result = {}
        
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s in self.result:
            return self.result[s]
            
        for i in range(len(s) - 1):
            if s[i:i+2] == "++":
                if not self.canWin(s[:i]+"--"+s[i+2:]):
                    ##just these two line to cache!!!! Done!
                    self.result[s[:i]+"--"+s[i+2:]] = False
                    self.result[s] = True
                    return True
        return False

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.