293. Flip Game

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 twoconsecutive"++"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"+--+".

思路：这种博弈类的问题，重点思想就是，你要Minimize你的对手的Profit。在这道题里面就是有点back tracking的思想，我flip一个如果我的对手不能赢的话，那么我就赢了。如果我怎么flip我都不能赢对手的话，那我就认输。

class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return self.bt(s)

    def bt(self, s):
        for i in range(len(s)-1):
            if s[i:i+2] == '++':
                if not self.bt(s[:i] + '--' + s[i+2:]):
                    return True
        return False