Flip Game II

Problem: Flip Game II

We can use backtracking and keeping toggle the returning result to get the answer. To reduce running time, we can use memoization with extra space.

Code in Python:

class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        cache = {}
        def helper(string):
            if string in cache: return cache[string]
            for i in xrange(1, len(string)):
                if string[i-1:i+1] == "++":
                    if not helper(string[:i-1]+"--"+string[i+1:]):
                        cache[string] = True
                        return True
            cache[string] = False
            return False
        return helper(s)