FlipGame [source code]

public class FlipGame {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == '+' && chars[i - 1] == '+') {
                res.add(s.substring(0, i - 1) + "--" + s.substring(i + 1));
            }
        }
        return res; 
    }
}

这个题目本身思路并不难, 不过在权衡用什么数据结构来做的时候, 值得多做一些思考; 刚开始我的想法是用StringBuilder来做, 不过后来想一想, 这里要的其实不是 mutability, 而是 immutability: 因为你要做出不同版本的new string value来丢到 result 里面去;

另外, public String substring(int beginIndex, int endIndex)这个 API 里面, 要记得endIndex是不包括的;

一个小问题, 注意这里的loop header里面的 i 的起点. 不要总是相当然的认为就是0; 一定要要成每次写 forloop 就脑子里迅速提问一下自己, 这里的 i 的起点应该是多少;

算法速度是1ms, 还算是可以接受的; submission 最优解的思路是:

                c[i]='-';  
                c[i+1]='-';  
                ans.add(new String(c));  
                c[i]='+';  
                c[i+1]='+';

就是 addd 完了之后再改回来, 类似用 mutability 来模拟 immutability. 这个没有什么好学习的, 完全没有我这个写法简洁.

这个是 disccusion 最优解:

public List<String> generatePossibleNextMoves(String s) {  
    List list = new ArrayList();  
    for (int i=-1; (i = s.indexOf("++", i+1)) >= 0; )  
        list.add(s.substring(0, i) + "--" + s.substring(i+2));  
    return list;  
}

跟我的算法核心思路是很相似的, 不过header用了一个比较巧妙的API:

int indexOf(String str, int fromIndex)  
Returns the index within this string of the first occurrence of the specified   
substring, starting at the specified index.

这个在substring search类的题目当中估计是格外好用的一个技巧;

Problem Description

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 [].

Seen this question in a real interview before? Yes No
Difficulty:Easy
Category:Algorithms
Acceptance:55.33%
Contributor: LeetCode
Topics:
String
You might like:
(M) Flip Game II
Company:
Google