Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2

Input: currentState = "+"
Output: false

Solution

Method 1 - Backtracking

To determine if the starting player can guarantee a win in the Flip Game, we will use a backtracking approach. The main idea is to recursively simulate the game: at each step, we flip two consecutive “++” into “–” and then check if the opponent can win from this new state. If there exists at least one move that results in a win for the starting player (i.e., forces the opponent to lose in the subsequent moves), then the starting player can guarantee a win.

Approach

  1. Recursive Backtracking:
    • Iterate through the string currentState to find all positions where “++” can be flipped to “–”.
    • For each valid move, flip “++” to “–” and recursively check if the opponent (starting player of the next turn) can guarantee a win from the new state.
    • If there is at least one move that causes all subsequent moves of the opponent to result in a loss, return true.
  2. Memoization:
    • Use memoization to store the results of previously computed states to avoid redundant computations and speed up the process.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean canWin(String currentState) {
        return canWin(currentState, new HashMap<>());
    }

    private boolean canWin(String state, Map<String, Boolean> memo) {
        if (memo.containsKey(state)) {
            return memo.get(state);
        }

        for (int i = 0; i < state.length() - 1; i++) {
            if (state.substring(i, i + 2).equals("++")) {
                String newState = state.substring(0, i) + "--" + state.substring(i + 2);
                if (!canWin(newState, memo)) {
                    memo.put(state, true);
                    return true;
                }
            }
        }

        memo.put(state, false);
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def canWin(self, currentState: str) -> bool:
        memo: Dict[str, bool] = {}
        return self.can_win(currentState, memo)
    
    def can_win(self, state: str, memo: Dict[str, bool]) -> bool:
        if state in memo:
            return memo[state]

        for i in range(len(state) - 1):
            if state[i:i+2] == "++":
                new_state = state[:i] + "--" + state[i+2:]
                if not self.can_win(new_state, memo):
                    memo[state] = True
                    return True
        
        memo[state] = False
        return False

Complexity

  • ⏰ Time complexity: O(n!), in the worst case, as each move can generate multiple recursive calls and the number of valid moves decreases factorially. However, with memoization, it improves significantly.
  • 🧺 Space complexity: O(n!), in the worst case due to the depth of the recursion tree and memoization storage.