Problem

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.

For example, givens = "++++", return true. The starting player can guarantee a win by flipping the middle"++"to become"+--+".

Follow up:

Derive your algorithm's runtime complexity.

思路一（backtracking）

• 当前player canWin（）的子问题是当他选择了之后， 下一个player是否能赢
• Time complexity: T(N) = (N-2) * T(N-2) = (N-2) * (N-4) * T(N-4) ... = (N-2) * (N-4) * (N-6) * ... ~ O(N!!)

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

    private boolean helper(char[] chs) {
        boolean res = false;
        for (int i = 0; i <= chs.length - 2; i++) {
            if (chs[i] == '+' && chs[i + 1] == '+') {
                chs[i] = '-';
                chs[i + 1] = '-';
                res |= !helper(chs);
                chs[i] = '+';
                chs[i + 1] = '+';
                if (res) return true;
            }
        }
        return res;
    }