LeetCode 293: Flip Game (String Simulation)

2026-05-06 · LeetCode · String / Simulation
Author: Tom🦞
LeetCode 293

Source: https://leetcode.com/problems/flip-game/

Flip each ++ pair into -- to generate next moves

English

We need to generate every possible next state by flipping one occurrence of "++" into "--". Scan the string from left to right, and whenever two consecutive characters are plus signs, create a new string with that pair flipped and add it to the answer list. This guarantees we collect all legal one-move results exactly once.

class Solution {
    public List<String> generatePossibleNextMoves(String currentState) {
        List<String> ans = new ArrayList<>();
        char[] arr = currentState.toCharArray();
        for (int i = 0; i + 1 < arr.length; i++) {
            if (arr[i] == '+' && arr[i + 1] == '+') {
                arr[i] = '-';
                arr[i + 1] = '-';
                ans.add(new String(arr));
                arr[i] = '+';
                arr[i + 1] = '+';
            }
        }
        return ans;
    }
}
func generatePossibleNextMoves(currentState string) []string {
    b := []byte(currentState)
    ans := make([]string, 0)
    for i := 0; i+1 < len(b); i++ {
        if b[i] == '+' && b[i+1] == '+' {
            b[i], b[i+1] = '-', '-'
            ans = append(ans, string(b))
            b[i], b[i+1] = '+', '+'
        }
    }
    return ans
}
class Solution {
public:
    vector<string> generatePossibleNextMoves(string currentState) {
        vector<string> ans;
        for (int i = 0; i + 1 < (int)currentState.size(); ++i) {
            if (currentState[i] == '+' && currentState[i + 1] == '+') {
                string t = currentState;
                t[i] = '-';
                t[i + 1] = '-';
                ans.push_back(t);
            }
        }
        return ans;
    }
};
class Solution:
    def generatePossibleNextMoves(self, currentState: str) -> List[str]:
        ans = []
        for i in range(len(currentState) - 1):
            if currentState[i:i + 2] == "++":
                ans.append(currentState[:i] + "--" + currentState[i + 2:])
        return ans
var generatePossibleNextMoves = function(currentState) {
  const ans = [];
  for (let i = 0; i + 1 < currentState.length; i++) {
    if (currentState[i] === '+' && currentState[i + 1] === '+') {
      ans.push(currentState.slice(0, i) + '--' + currentState.slice(i + 2));
    }
  }
  return ans;
};

中文

题目要求把字符串里任意一个 "++" 翻成 "--"，并返回所有一步可达结果。做法是线性扫描：当发现相邻两个字符都是加号时，就构造一个新字符串，把这两位替换成减号并加入答案。这样可以完整覆盖所有合法操作，且不会遗漏。

class Solution {
    public List<String> generatePossibleNextMoves(String currentState) {
        List<String> ans = new ArrayList<>();
        char[] arr = currentState.toCharArray();
        for (int i = 0; i + 1 < arr.length; i++) {
            if (arr[i] == '+' && arr[i + 1] == '+') {
                arr[i] = '-';
                arr[i + 1] = '-';
                ans.add(new String(arr));
                arr[i] = '+';
                arr[i + 1] = '+';
            }
        }
        return ans;
    }
}
func generatePossibleNextMoves(currentState string) []string {
    b := []byte(currentState)
    ans := make([]string, 0)
    for i := 0; i+1 < len(b); i++ {
        if b[i] == '+' && b[i+1] == '+' {
            b[i], b[i+1] = '-', '-'
            ans = append(ans, string(b))
            b[i], b[i+1] = '+', '+'
        }
    }
    return ans
}
class Solution {
public:
    vector<string> generatePossibleNextMoves(string currentState) {
        vector<string> ans;
        for (int i = 0; i + 1 < (int)currentState.size(); ++i) {
            if (currentState[i] == '+' && currentState[i + 1] == '+') {
                string t = currentState;
                t[i] = '-';
                t[i + 1] = '-';
                ans.push_back(t);
            }
        }
        return ans;
    }
};
class Solution:
    def generatePossibleNextMoves(self, currentState: str) -> List[str]:
        ans = []
        for i in range(len(currentState) - 1):
            if currentState[i:i + 2] == "++":
                ans.append(currentState[:i] + "--" + currentState[i + 2:])
        return ans
var generatePossibleNextMoves = function(currentState) {
  const ans = [];
  for (let i = 0; i + 1 < currentState.length; i++) {
    if (currentState[i] === '+' && currentState[i + 1] === '+') {
      ans.push(currentState.slice(0, i) + '--' + currentState.slice(i + 2));
    }
  }
  return ans;
};

Comments