Python solution with detailed explanation


  • 0
    G

    Solution

    Flip Game II https://leetcode.com/problems/flip-game-ii/?tab=Description

    Brute Force: Backtracking

    1. Simple backtracking solution. This is O(N!). https://discuss.leetcode.com/topic/27282/theory-matters-from-backtracking-128ms-to-dp-0ms
    2. Note that we reset the string before we test next_result. This is critical and failing this could result in bugs.
    class Solution(object):
        def helper(self, s):
            for i in range(len(s)-1):
                if s[i] == s[i+1] and s[i] == "+":
                    s[i] = s[i+1] = "-"
                    next_result = self.helper(s)
                    s[i] = s[i+1] = "+"
                    if next_result == False:
                        return True
            return False
        
        def canWin(self, s):
            """
            :type s: str
            :rtype: bool
            """
            return self.helper([ch for ch in s])
    

    Memoization

    • Throw in a cache.
    class Solution(object):
        def helper(self, s, cache):
            cache_key = "".join(s)
            if cache_key in cache:
                return cache[cache_key]
            for i in range(len(s)-1):
                if s[i] == s[i+1] and s[i] == "+":
                    s[i] = s[i+1] = "-"
                    next_result = self.helper(s, cache)
                    s[i] = s[i+1] = "+"
                    if next_result == False:
                        cache[cache_key] = True
                        return True
            cache[cache_key] = False
            return cache[cache_key]
        
        def canWin(self, s):
            """
            :type s: str
            :rtype: bool
            """
            cache = {}
            return self.helper([ch for ch in s], cache)
    

Log in to reply
 

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