LeetCode – Flip Game II

Tags: ,

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.

Analysis

We can use a recursive algorithm to solve this problem. The basic idea is that for each valid move, we check whether the other player can win. If the first player finds a move that can make the second player looses, the first player wins. Otherwise, the first player looses. In the process, the second player will take the same strategy. See the following java code.

Java Solution

A better solution is using backtrack:

We can also use memorization to improve the algorithm further. 

Time complexity

T(N) = T(N-2) + T(N – 3) + [T(2) + T(N – 4)]  + [T(3) + T(N – 5)] + … [T(N4) + T(2)] + T(N3) + T(N2) = 2 * sum(T[i]) (i =3..N2)

As we have T(1) = 1, T(2) = 1, T(3) = 2 * (T(1)) = 2, T(4) = 2 *(T(2) + T(1)) = 2, T(5) = 2 * (T(2) + T(3))

So the above formula is similar to the geometric sequence, So the time complexity is  2^N.