Problem Description:

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.

---

The simplest solution that I have found is (refer to the first paragraph for explanations of the idea and the Java code). I rewrite it in C++.

The idea is very straightforward: if you can make s non-winnable by a move, then you will win.

1 class Solution {2 public:3     bool canWin(string s) {4         for (int i = -1; (i = s.find("++", i + 1)) >= 0; )5             if (!canWin(s.substr(0, i) + '-' + s.substr(i+2)))6                 return true;7         return false;8     }9 };

If you are interested to learn more, shares a more sophisticated solution using game theory (it reduces the running time to 0 seconds!). The code is restructured as below.

1 class Solution { 2 public: 3     bool canWin(string s) { 4         vector
     
       states = gameStates(s); 5         if (states.empty()) return false; 6          return spragueGrundy(states) != 0; 7     } 8 private: 9     vector
      
        gameStates(string& s) {10         vector
       
         states;11         int n = s.length(), c = 0;12         for (int i = 0; i < n; i++) {13             if (s[i] == '+') c++;14             if (i == n - 1 || s[i] == '-') {15                 if (c >= 2) states.push_back(c);16                 c = 0;17             }18         }19         return states;20     }21     int firstMissingNumber(unordered_set
        
         & st) {22         int m = st.size();23         for (int i = 0; i < m; i++)24             if (!st.count(i)) return i;25         return m;26     }27     int spragueGrundy(vector
         
          & states) {28         int m = *max_element(states.begin(), states.end());29         vector
          
            sg(m + 1, 0);30 for (int l = 2; l <= m; l++) {31 unordered_set
           
             st;32 for (int l1 = 0; l1 < l / 2; l1++) {33 int l2 = l - l1 - 2;34 st.insert(sg[l1] ^ sg[l2]);35 }36 sg[l] = firstMissingNumber(st);37 }38 int v = 0;39 for (int state : states) v ^= sg[state];40 return v;41 }42 };