Article From:https://www.cnblogs.com/yaoyudadudu/p/9216170.html

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

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *