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

.

Follow up:

Derive your algorithm’s runtime complexity.

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; } };