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.

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

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

Follow up:

Derive your algorithm's runtime complexity.

解题方法

这一题有点像Lintcode上的coins in a line，也是判断先行动的人是否能够确保最后胜利的题目，所以应该也可以用DP解。 但是这里backtracking的解法更直观，只不过之间复杂度比较高，是O(n^2)

recursive

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

DP

Solution

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

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

        return False

Reference