294. Flip Game II

link

First thought

class Solution:
    def canWin(self, currentState: str) -> bool:

        n = len(currentState)

        if n == 1:
            return False

        @cache
        def backtrack(s, c):
            if c == 0:
                res = False, True
            else:
                res = True, False

            for i in range(1, len(s)):
                if s[i-1:i+1] == '++':
                    res = backtrack(s[:i-1] + '--' + s[i+1:], (c + 1) % 2)

                    if c == 0 and res[0]:
                        return res
                    if c == 1 and res[1]:
                        return res

            return res


        p1, p2 = backtrack(currentState, 0)

        return p1

Copy from discussion

class Solution:
    def canWin(self, s: str) -> bool:
        
        @cache
        def fn(s): 
            """Return True if player can win by playing optimally."""
            if "++" not in s: return False # already lost 
            for i in range(len(s)-1): 
                if s[i:i+2] == "++" and not fn(s[:i] + "--" + s[i+2:]): return True 
            return False 
        
        return fn(s)