[LintCode] Problem 914 - Flip Game

Posted on | In ,

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

No.1

Input: s = “++++”

Output: 

1
2
3
4
5
[
  "--++",
  "+--+",
  "++--"
]

No.2

Input: s = “—+++-+++-+”

Output: 

1
2
3
4
5
6
[
	"---+++-+---+",
	"---+++---+-+",
	"---+---+++-+",
	"-----+-+++-+"
]

Code

1
2
3
4
5
6
7
8
9
10
11
12
public List<String> generatePossibleNextMoves(String s) {
    List<String> result = new ArrayList<>();

    int idx = s.indexOf("++", 0);

    while (idx != -1) {
        result.add(s.substring(0, idx) + "--" + s.substring(idx + 2));
        idx = s.indexOf("++", idx + 1);
    }

    return result;
}