Question
Formatted question description: https://leetcode.ca/all/293.html
293 Flip Game
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.
For example, given s = "++++", after one move, it may become one of the following states:
(input string可以有'-',比如"+++--++")
[
"--++",
"+--+",
"++--"
]
If there is no valid move, return an empty list [].
Algorithm
Start traversing from the second letter, each time it is judged whether the current letter is +, and the previous letter is +, if both are plus, the reversed string will be stored in the result.
Code
Java
import java.util.ArrayList;
import java.util.List;
public class Flip_Game {
public class Solution {
public List<String> generatePossibleNextMoves(String s) {
List<String> result = new ArrayList<>();
char[] arr = s.toCharArray();
// solution-1: restore
for(int i = 1; i < s.length(); i++) {
if(arr[i] == '+' && arr[i - 1] == '+') {
arr[i] = '-';
arr[i - 1] = '-';
result.add(String.valueOf(arr));
arr[i] = '+'; // @note: need to resulttore
arr[i - 1] = '+';
}
}
// solution-2: just concatenate, no restore
for(int i = 1; i < s.length(); i++) {
if(arr[i] == '+' && arr[i - 1] == '+') {
result.add(s.substring(0, i - 1) + "--" + s.substring(i + 1));
}
}
return result;
}
}
}