294. 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.

Solution: DFS

class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        memo = dict()

        def can_win(s):
            if s not in memo:
                # any lost for opponent
                memo[s] = any(not can_win(move) for move in self.moves(s))
            return memo[s]

        return can_win(s)

    def moves(self, s):
        pre = ''
        for idx, cur in enumerate(s):
            if cur == pre == '+':
                yield '{}{}{}'.format(s[:idx - 1], '--', s[idx + 1:])
            pre = cur

Lessons:

• Time complexity is $O(n!)$. For a string like ++++++, we have 5 moves for player one, then we have 3 moves for player two, then we have 1 move for player one. So the time complexity is $n \times (n - 2) \times (n - 4) ... \times 1$ .

Related:

• 293. Flip Game