LeetCode Q294: 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:

Using backtracking. In each new call to the function, we only consider whether current player can win by flipping two signs in current configuration. Then we return the result to the last function call. Don't confusing yourself by setting up the order of the players.