Flip Game II

题目描述

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.

解题方法

这一题有点像Lintcode上的coins in a line，也是判断先行动的人是否能够确保 最后胜利的题目，所以应该也可以用DP解。

但是这里backtracking的解法更直观，只不过之间复杂度比较高。

dfs

将canWin(self, s)看为当start string为s的时候第一个行动的人是否能确保赢， 那么能够确保赢的条件就是，当有一个"++"被替换后 的s1, 当start string为s1的 时候先行动的人确保会输（这时候先行动的是第二个人了）。 对于s中的所有++都尝试一下，递归就能够 找到结果。

记忆化搜索优化

根据记忆化搜索的思想，可以将dfs的结果存到一个表里，如果当前这个结果已经 计算过，就直接取出结果即可，可以省去很多重复计算。

DP

Solution

记忆化搜索 + DFS

136 ms

class Solution(object):


    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        self.dp = {}
        if not s:
            return False

        self.helper(s)
        return self.dp[s]

    def helper(self, s):
        if str(s) in self.dp:
            return self.dp[str(s)]

        for i in range(len(s)-1):
            if s[i:i+2] == "++" and not self.helper(s[:i] + "--" + s[i+2:]):
                self.dp[str(s)] = True
                return True

        self.dp[str(s)] = False
        return False

Reference