0294. Flip Game II

https://leetcode.com/problems/flip-game-ii

Description

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' 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.

Return true if the starting player can guarantee a win, and false otherwise.

Example 1:

**Input:** currentState = "++++"
**Output:** true
**Explanation:** The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Example 2:

**Input:** currentState = "+"
**Output:** false

Constraints:

• 1 <= currentState.length <= 60

• currentState[i] is either '+' or '-'.

Follow up: Derive your algorithm's runtime complexity.

ac1: backtracking

This key point if (!nextCanWin) return true; is the most important breakthrough point。

class Solution {
    public boolean canWin(String s) {
        boolean[] str = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            str[i] = s.charAt(i) == '+' ? true : false;
        }

        return canWinHelper(str);
    }

    private boolean canWinHelper(boolean[] str) {
        // exit
        if (str.length < 2) return false;

        for (int i = 0; i < str.length - 1; i++) {
            if (str[i] && str[i+1]) {
                str[i] = false;
                str[i+1] = false;
                boolean nextCanWin = canWinHelper(str);
                str[i] = true;
                str[i+1] = true;

                if (!nextCanWin) return true;
            }
        }

        return false;
    }
}