圖：新生大學

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

input: a string with only + and - two kinds of characters
output: for a given input, based on the game rule, return whether there is one strategy that can make the first player win, if yes, return true, if there is none, return false
corner: when the string if null, return false

We will first change the string to a character array.

And apply Backtracking algorithm to solve it.

The starting point of the first player will iterate from 0 to arr.length - 2, when he finds two consecutive ++, he will soon change it into --.

Then the second player will do the same thing, so we pass current changed array to the second player, and he will receive a result: boolean otherWin = helper(arr);

If the second player will win, means he will return a true to upper level, the first player should recover his current strategy by change the -- to original ++, and keep moving i to next step, so that he can find other strategy that will make himself finally win the game, as long as there is just one strategy make it happen, the final result will be true, otherwise, it will be false.

public class Solution{
    public boolean canWin(String s){
        //corner
        if ( s == null || s.length() == 0 ){
            return false;
        }
        
        return helper(s.toCharArray());
    }
    
    public boolean helper(char[] arr){
        for ( int i = 0; i < arr.length; i++ ){
            if ( arr[i] == '+' && arr[i + 1] == '+' ){
                arr[i] = '-';
                arr[i + 1] = '-';
                
                boolean otherWin = helper(arr);         //2人輪流
                
                arr[i] = '+';               //返回到upper level后恢復＋號
                arr[i + 1] = '+';
                
                if ( !otherWin ){           //另一人false時走這一步峭火，另一人true時搀绣，要繼續(xù)遍歷＋＋對
                    return true;            //直到找到某一種走法可以讓另一人false燎竖，最終整體返回的值為true习柠，此時第一人贏
                }
            }
        }
        
        return false;           //如果遍歷到頭沒有＋＋對了单刁，而且?guī)追N走法都一直找不到贏的走法了捉超，第一人就最終false
    }
}