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, givens = "++++", return true. The starting player can guarantee a win by flipping the middle"++"to become"+--+".
Follow up:  Derive your algorithm's runtime complexity.

思路是先反转一下， 判断对手输赢状态， 把刚刚反转的回溯成最初的字符串， 免得影响下一个循环结果。 如果确定对手输了， 那我们一定赢了， 直到循环结束，都没发现对手输， 那一定是我们输了。