293. Flip Game

Description of the problem:

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.

Example:

```Input: `s = "++++"`
Output:
[
"--++",
"+--+",
"++--"
]
```

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

The idea of solving the problem:

Traverse the string.

One thing to note is that s.size () returns the type of size_t, which is actually an unsigned integer.

When it is equal to 0, the value obtained here is s.size () – 1.18446744073709551615

You can jump into the loop at this time, and there will be a mistake!

Code:

```class Solution {
public:
vector<string> generatePossibleNextMoves(string s) {
vector<string> ret;
int n = s.size();
for(int i = 0; i < n - 1;i++){
if(s[i] == '+' && s[i+1] == '+'){
string temp = s;
temp[i] = '-';
temp[i+1] = '-';
ret.push_back(temp);
}
}
return ret;
}
};```

—————-The next segmentation line – — – —

294. Flip Game II

Description of the problem:

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

The idea of solving the problem:

At the beginning, I got the wrong way to solve the problem. Because I came from 292. Nim Game, I thought I should use DP or some other clever method.

Then there is a process of understanding the wrong idea.

The string given in this question contains both ‘+’ and ‘-‘.

So we can use enumerations to check.

And if only one can win, then we can win.

Code:

```class Solution {
public:
bool canWin(string s) {
for(int i = 1; i < s.size(); i++){
if(s[i] == '+' && s[i-1] == '+' &&  !canWin(s.substr(0, i-1) + "--"+ s.substr(i+1)))
return true;
}
return false;
}
};```

We use memory search to optimize and avoid repeated search.

```class Solution {
public:
bool canWin(string s) {
unordered_map<string, bool> m;
return dfs(s, m);
}
bool dfs(string& s, unordered_map<string, bool>& m){
if(m.count(s)) return m[s];
for(int i=1; i<s.size(); i++){
if(s[i-1]=='+' && s[i]=='+'){
s[i-1] = '-'; s[i] = '-';
if(!dfs(s, m)) {
s[i-1] = '+'; s[i] = '+';
m[s] = true;
return true;
};
s[i-1] = '+'; s[i] = '+';
}
}
m[s] = false;
return false;
}
};```