翻转游戏

题目

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;  
    }  
}