Thinking process

recursively finding a solution that makes the second player can't win

• iterate over each possible way of flipping
• pass down the flipping result, if it returns false, which means the second player can't win, if it returns true, keep finding next solution.

Time Complexity

O (n!!) => T(n) = (n - 1) * (n - 3) * (n - 5) ..., which is double factorial

https://en.wikipedia.org/wiki/Double_factorial

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

    private boolean canWinHelper(char[] chars) {
        for (int i = 1; i < chars.length; ++i) {
            if (chars[i] == '+' && chars[i - 1] == '+') {
                chars[i] = '-';
                chars[i - 1] = '-';

                boolean win = canWinHelper(chars);

                chars[i] = '+';
                chars[i - 1] = '+';

                if (!win) {
                    return true;
                }
            }
        }

        return false;
    }
}