Skip to content

Latest commit

 

History

History

293

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

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 [].

Companies:
Google

Related Topics:
String

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/flip-game/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        vector<string> ans;
        for (int i = 1, N = s.size(); i < N; ++i) {
            if (s[i] != '+' || s[i - 1] != '+') continue;
            ans.push_back(s);
            ans.back()[i] = ans.back()[i - 1] = '-';
        }
        return ans;
    }
};