Skip to content

293. Flip Game 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  vector<string> generatePossibleNextMoves(string currentState) {
    vector<string> ans;

    for (int i = 0; i + 1 < currentState.length(); ++i)
      if (currentState[i] == '+' && currentState[i + 1] == '+')
        ans.push_back(currentState.substr(0, i) + "--" +
                      currentState.substr(i + 2));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public List<String> generatePossibleNextMoves(String currentState) {
    List<String> ans = new ArrayList<>();

    for (int i = 0; i + 1 < currentState.length(); ++i)
      if (currentState.charAt(i) == '+' && currentState.charAt(i + 1) == '+') {
        StringBuilder sb = new StringBuilder(currentState);
        sb.setCharAt(i, '-');
        sb.setCharAt(i + 1, '-');
        ans.add(sb.toString());
      }

    return ans;
  }
}

1
2
3
4
5
class Solution:
  def generatePossibleNextMoves(self, currentState: str) -> list[str]:
    return [currentState[:i] + '--' + currentState[i + 2:]
            for i, (a, b) in enumerate(zip(currentState, currentState[1:]))
            if a == '+' and b == '+']