Python solution using DFS and memo(easy to follow)


  • 1

    Try every feasible '++' to flip, If there is at least one choice that the opponent can't win. Return True. Using memo to cache.

    class Solution(object):
        def canWin(self, s):
            """
            :type s: str
            :rtype: bool
            """
            self.memo = {}
            return self.dfs(s)
    
        def dfs(self, s):
    
            if s not in self.memo:
    
                if '++' not in s:
                    return False
    
                res = []
                for i in range(len(s)-1):
                    if s[i:i+2] == '++':
                        res.append(self.dfs(s[:i]+'--'+s[i+2:]))
                self.memo[s] = not all(res) # if there is a False in res
    
            return self.memo[s]
    

    Another version

    class Solution(object):
        def canWin(self, s):
            """
            :type s: str
            :rtype: bool
            """
            self.memo = {}
            return self.dfs(s)
    
        def dfs(self, s):
            if s not in self.memo:
                if '++' not in s:  # base case
                    return False
                for i in range(len(s)-1):
                    if s[i:i+2] == '++':
                        if not self.dfs(s[:i]+'--'+s[i+2:]): # if oppo can't win
                            self.memo[s] = True
                            return self.memo[s] # then return True
                self.memo[s]=False  # tried every step still can't win
            return self.memo[s]
    

Log in to reply
 

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