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.







class Solution {
public:
    unordered_map<string,bool>hash;
    bool canWin(string s) {
        return dfs(s,0);
    }
    
    bool dfs(string &s,int turn){
        string state=s+","+to_string(turn);
        if(hash.find(state)!=hash.end())return hash[state];
        int next=1;
        if(turn==1)next=0;
        bool res=false;
        for(int i=1;i<s.size();i++){
            if(s[i]==s[i-1]&&s[i]=='+'){
                s[i]='-';s[i-1]='-';
                bool val=dfs(s,next);
                if(val==false){
                    res=true;
                }
                s[i]='+';s[i-1]='+';
            }
        }
        hash[state]=res;
        return res;
    }
};