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 determine if the starting player can guarantee a win.

这道题的思路比较绕，只要递归就可以，如果当前的string没有下一个状态了，就return false。如果有，检查所有下一个状态，递归调用canWin, 如果有一个下一状态返回的是false，那么说明对手在这一状态下无法取胜，说明starting player一定可以赢，return true。都可能赢的话就return false

class Solution {
    public boolean canWin(String s) {
        List<String> next = generatePossibleNextMoves(s);
        if(next.size() == 0)
            return false;

        for(String n: next) {
            if(!canWin(n))
                return true;
        }

        return false;
    }

    public List<String> generatePossibleNextMoves(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length() < 2)
            return res;

        char[] cs = s.toCharArray();
        for(int i = 0; i < cs.length - 1; i++) {
            if(cs[i] == cs[i + 1] && cs[i] == '+') {
                cs[i] = '-';
                cs[i + 1] = '-';

                res.add(String.valueOf(cs));
                cs[i] = '+';
                cs[i + 1] = '+';
            }
        }

        return res;
    }
}

也可以写成backtracking的形式

class Solution {
    public boolean canWin(String s) {
        return canWin(s.toCharArray());
    }

    public boolean canWin(char[] cs) {
        for(int i = 0; i < cs.length - 1; i++) {
            if(cs[i] == cs[i + 1] && cs[i] == '+') {
                cs[i] = '-';
                cs[i + 1] = '-';

                if(!canWin(cs)) {
                    cs[i] = '+';
                    cs[i + 1] = '+';
                    return true;
                } else {
                    cs[i] = '+';
                    cs[i + 1] = '+';
                }
            }
        }

        return false;
    }
}