L 294. Flip Game II -------------M

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.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:

Derive your algorithm's runtime complexity. 

A:

 典型的backtrack

每次更改2个位置，然后看剩下的是不是怎么变化也赢不了。

class Solution {
public:
    bool canWin(string s) {
        return helper(s);
    }
private:
    bool helper(string &s){
        for(int i =0;i+1<s.length();i++){
            if(s[i]=='+' && s[i+1]=='+'){
                s[i]=s[i+1] = '-';
                if(not helper(s)){
                    s[i]=s[i+1] = '+';//put back  Also need put back
                    return true;
                }
                s[i]=s[i+1] = '+';//put back
            }
        }
        return false;
    }
};

Mistakes:

上面的 写成  for(int i =0;i<s.length() -1 ;i++)  就会不对， 仔细想想为什么。  对于"" 的输入。

***************method 2*******************

数出 ++ 的个数。 分别计算

如果是2，3.只能一个move。 如果是4， first Player可以选择留给1个还是0个。