【Leetcode】 Flip Game 翻转游戏

雨点打透心脏的1/2处 2022-07-17 04:40 166阅读 0赞

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:

[
      "--++",
      "+--+",
      "++--"
    ]

If there is no valid move, return an empty list `[]`.

解析：

这道题让我们把相邻的两个++变成--，真不是一道难题，我们就从第二个字母开始遍历，每次判断当前字母是否为+，和之前那个字母是否为+，如果都为加，则将翻转后的字符串存入结果中即可

**Solution: **

Just iterate the string characters and check the element at i and i + 1 are '+'.

Time complexity : O(n)

Space complexity: O(n) (worst)

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **class** Solution \{  
2.      **public** List<String> generatePossibleNextMoves(String s) \{  
3.          List<String> result = **new** ArrayList<String>();  
4.          **for** (**int** i = 0; i < s.length() - 1; i++) \{  
5.              **if** (s.charAt(i) == '+' && s.charAt(i + 1) == '+') \{  
6.                  String flip = s.substring(0, i) + "--" + s.substring(i + 2);  
7.                  result.add(flip);  
8.              \}  
9.          \}  
10.         **return** result;  
11.     \}  
12. \}  
13.

[view plain]: http://blog.csdn.net/dolphin_wby/article/details/50336883#