294.Flip Game II

Tags: [try_best], [max_min], [win_lose], [game], [gaming], [top_to_bottom_dp], [DP], [memo], [DFS], [backtracking]

Com: {g}

Link: https://leetcode.com/problems/flip-game-ii/#/description

You are playing the following Flip Game with your friend: Given a string that contains only these two characters:+and-, you and your friend take turns to flip two consecutive"++"into"--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, givens = "++++", return true. The starting player can guarantee a win by flipping the middle"++"to become"+--+".

Follow up:
Derive your algorithm's runtime complexity.

Solution: DFS, Backtracking, DP, Memo

class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s or len(s) < 2:
            return False

        chars = list(s)
        memo = {}
        return self.can_win_helper(chars, memo)

    def can_win_helper(self, chars, memo):
        state = tuple(chars)
        if state in memo:
            return memo[state]

        for i in xrange(len(chars) - 1):
            if chars[i] == chars[i + 1] == '+':
                chars[i], chars[i + 1] = '-', '-'
                if not self.can_win_helper(chars, memo):
                    chars[i], chars[i + 1] = '+', '+'
                    return True
                chars[i], chars[i + 1] = '+', '+'

        memo[state] = False
        return False

Revelation:

• Define the recursion as that if the current player try his best, return he can win or not. 定义recursion function的meaning是如果当前player does his best，return 他是否能赢，这样定以后，在recursion里我们可以让当前player试遍所有可能的动作，然后call recursion 把改完后的chars交给对手，因为recursion被定义为player做到最好return能否赢，所以一旦找到一种情况可以让对手在已经做到最好的决策的情况下输，那么当前player就可以return True(一定能找到一种方法赢对手).
• The reason we are using memo, because there exists overlapping computing, think about, for example, the current chars = ['+', '+', '+', '+', '-', '-', '-', '-', '+'], there are many ways the two players can make the current chars.

Note:

• Time complexity = O(n!!) this is called 'double factorial' or 'semifactorial' (https://en.wikipedia.org/wiki/Double\_factorial\).
• At very beginning, there are n '+', so there are (n - 1) ways, and once we flip the '++' to '--', there are (n - 2) - 1 ways to flip, so the T = (n - 1) * (n - 3) * (n - 5) ... = O(n!!).