# [leetcode] Flip Game I && II

### Flip Game

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 compute all possible states of the string after one valid move.

For example, given `s = "++++"`, after one move, it may become one of the following states:

```[
"--++",
"+--+",
"++--"
]
```

If there is no valid move, return an empty list `[]`.

Just check whether two adjacent characters are the same and they are equal to ‘+’.

```class Solution {
public:
vector<string> generatePossibleNextMoves(string s) {
vector<string> ans;
if(s.size() <= 1) return ans;
char prev = s;
for(int i = 1; i < s.size(); i++)
{
char curr = s[i];
if(prev == curr && prev == '+'){
ans.push_back(flip(s, i - 1));
}
prev = curr;
}
return ans;
}
string flip(string s, int i){
s[i] = s[i + 1] = '-';
return s;
}
};```

### Flip Game II

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 `"+--+"`.

Actually, we can merge playerMove and enemyMove. But I split them to make the program more clear ans self-explained.

O(n!)

```class Solution {
public:
bool canWin(string s) {
return playerMove(s);
}
//return true if player can win
bool playerMove(string s){
vector<int> idxs = findFlips(s);
for(int i : idxs){
string news = flip(s, i);
if(enemyMove(news) == false){
return true;
}
}
return false;
}
//return true if enemy can win
bool enemyMove(string s){
vector<int> idxs = findFlips(s);
for(int i : idxs){
string news = flip(s, i);
if(playerMove(news) == false){
return true;
}
}
return false;
}
vector<int> findFlips(string & s){
vector<int> ans;
if(s.size() <= 1) return ans;
char prev = s;
for(int i = 1; i < s.size(); i++){
char curr = s[i];
if(prev == curr && curr == '+'){
ans.push_back(i - 1);
}
prev = curr;
}
return ans;
}
string flip(string s, int i){
s[i] = s[i + 1] = '-';
return s;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.