flip-game

Flip Game – LeetCode 293

Problem

Description

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.

Answer

Original

Code

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

思路

简单的遍历整个s，对相连的++进行翻转就得到了一个答案。时间复杂度$O(n)$，空间复杂度$O(n)$。

Better

思路

还没看到更好的思路。