294. Flip Game II

The idea is to exhaust all the ways by backtracking. As long as there is a way to prevent the other from winning, we stop the backtracking.

1:  class Solution {  
2:  private:  
3:    string ss;  
4:    int len;  
5:  public:  
6:    bool canWin(string s) {  
7:      len = s.size();  
8:      ss = s;  
9:      return helper();  
10:    }  
11:    bool helper() {  
12:      for (int i = 0; i < len-1; i++) {  
13:        if (ss[i] == '+' && ss[i+1] == '+') {  
14:          ss[i] = ss[i+1] = '-'; // make the move  
15:          bool win = helper();  
16:          ss[i] = ss[i+1] = '+'; // restore the move  
17:          if (!win) return true;  
18:        }  
19:      }  
20:      return false;  
21:    }  
22:  };  

When I revisited this code, I got much conciser code:

1:  class Solution {  
2:  public:  
3:    bool canWin(string s) {  
4:      for (int i = 0; i+1 < s.size(); i++) {  
5:        if (s[i] == '+' && s[i+1] == '+') {  
6:          s[i] = s[i+1] = '-';  
7:          if (!canWin(s)) return true;  
8:          s[i] = s[i+1] = '+';  
9:        }  
10:      }  
11:      return false;  
12:    }  
13:  };