翻转游戏
题目
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 twoconsecutive "++" 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 [].
你正在和你的朋友玩儿下面的翻转游戏:给定一个仅包含+和-的字符串,你和你的朋友轮流可以将"++"变成"--".当一个人没办法再行动的时候游戏就结束了,另一个人就赢了.
写一个方法来计算在一个合法的移动后的所有的可能状态.
例如,给定s="++++",一个移动之后,下面是可能出现的状态
[
"--++",
"+--+",
"++--"
]
如果没有合法的移动,返回一个空集合即可.
思路
刚开始会以为计算谁会赢,会涉及到动态规划,但是题目的意思是计算一个合法的移动后的所有的可能状态,因此我们只需要遍历s,判断即可
代码
public class Solution {
public List<String> generatePossibleNextMoves(String s) {
List<String> result = new ArrayList<String>();
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
String flip = s.substring(0, i) + "--" + s.substring(i + 2);
result.add(flip);
}
}
return result;
}
}
