Flip Game II(Medium)

Given a string that contains only + or - characters, each player takes turn to flip two consecutive "++" to "--".

The player who could not make a move loses.

Write a function that determines if the starting player can guarantee a win.

An example of a valid input string is "---++----++-+"

保证p1能胜利，就必须保持所有p2的move都不能赢。同时，p1只要在可走的Move里面，有一个move可以赢就足够了。

解法1 if you can make s non-winnable by a move, then you will win

public boolean canWin(String s) {
    for (int i=-1; (i = s.indexOf("++", i+1)) >= 0; )
        if (!canWin(s.substring(0, i) + "-" + s.substring(i+2)))
            return true;
    return false;
}

解法2：At first glance, backtracking seems to be the only feasible solution to this problem. We can basically try every possible move for the first player (Let's call him 1P from now on), and recursively check if the second player 2P has any chance to win. If 2P is guaranteed to lose, then we know the current move 1P takes must be the winning move. The implementation is actually very simple:

public boolean canWin(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }

        char[] arr = s.toCharArray();

        return canWinHelper(arr);
    }

    private boolean canWinHelper(char[] arr) {
        int i = 0;

        for (i = 0; i < arr.length - 1; i++) {
            if (arr[i] == '+' && arr[i + 1] == '+') {
                arr[i] = '-';
                arr[i + 1] = '-';

               boolean win = !canWinHelper(arr);

                arr[i] = '+';
                arr[i + 1] = '+';

                if (win) {
                    return true;
                }
            }
        }

        return false;
    }

References

1. Leetcode: Flip Game II

2 Leetcode Discussion for this issue