LeetCode 294: Flip Game II

Problem Restatement

We are given a string currentState containing only:

"+"
"-"

Two players take turns.

On each turn, a player chooses two consecutive plus signs:

"++"

and flips them into:

"--"

The player who cannot make a move loses.

We start first. We need to return whether the starting player can guarantee a win.

The source statement defines the game this way: players take turns flipping two consecutive "++" into "--", and the game ends when a player can no longer move. The player unable to move loses.

Input and Output

Function shape:

class Solution:
    def canWin(self, currentState: str) -> bool:
        ...

Examples

For:

currentState = "++++"

The starting player can win.

One winning move is to flip the middle pair:

"++++" -> "+--+"

Now the other player has no "++" left, so they cannot move.

Return:

True

For:

currentState = "+"

There is no "++" pair.

The starting player cannot move.

Return:

False

For:

currentState = "++"

The starting player flips the only pair:

"++" -> "--"

The other player cannot move.

Return:

True

First Thought: Try Every Move Recursively

This is a two-player game.

A position is winning if there exists at least one move that leaves the opponent in a losing position.

A position is losing if every possible move leaves the opponent in a winning position.

So we can recursively try every valid move.

class Solution:
    def canWin(self, currentState: str) -> bool:
        for i in range(len(currentState) - 1):
            if currentState[i:i + 2] == "++":
                next_state = currentState[:i] + "--" + currentState[i + 2:]

                if not self.canWin(next_state):
                    return True

        return False

This is correct, but it recomputes the same states many times.

For example, flipping pair A then pair B can reach the same state as flipping pair B then pair A.

Key Insight

Use memoization.

Store the result for each game state:

state -> can current player force a win?

Then, before solving a state, check whether we already know the answer.

This turns repeated recursive work into a lookup.

The rule remains the same:

current state is winning
if any next state is losing for the opponent

Algorithm

Define a recursive function:

dfs(state)

It returns whether the player to move can force a win from state.

For each index i:

1. If state[i:i + 2] == "++", create the next state.
2. Recursively check whether the opponent can win from that next state.
3. If the opponent cannot win, return True.

If no move leads to an opponent loss, return False.

Memoize each result.

Correctness

The game state fully determines whose position is winning or losing because both players have the same legal moves and the same objective.

If a state has no valid "++" move, the current player cannot move, so the state is losing. The algorithm returns False in this case.

If a state has at least one move to a losing state for the opponent, the current player can choose that move and force a win. The algorithm detects this by checking:

if not dfs(next_state):
    return True

If every possible move leads to a winning state for the opponent, then no matter what the current player does, the opponent can force a win. The algorithm returns False.

The recursion tries every legal move, so it misses no winning move. Memoization only reuses previously computed correct results for identical states.

Therefore the algorithm returns True exactly when the starting player can guarantee a win.

Complexity

Let:

n = len(currentState)

Each state scans the string to find valid moves.

Memoization greatly reduces repeated work, but the number of distinct states can still be exponential in the worst case.

Implementation

class Solution:
    def canWin(self, currentState: str) -> bool:
        memo = {}

        def dfs(state: str) -> bool:
            if state in memo:
                return memo[state]

            for i in range(len(state) - 1):
                if state[i:i + 2] == "++":
                    next_state = state[:i] + "--" + state[i + 2:]

                    if not dfs(next_state):
                        memo[state] = True
                        return True

            memo[state] = False
            return False

        return dfs(currentState)

Code Explanation

We store solved states here:

memo = {}

The recursive function answers whether the current player can win from state:

def dfs(state: str) -> bool:

If we have already solved the state, we return the cached answer:

if state in memo:
    return memo[state]

Then we scan every adjacent pair:

for i in range(len(state) - 1):

A move is legal only when the pair is "++":

if state[i:i + 2] == "++":

We create the next state by flipping that pair:

next_state = state[:i] + "--" + state[i + 2:]

If the opponent loses from that next state:

if not dfs(next_state):

then the current state is winning.

If no winning move is found, this state is losing:

memo[state] = False
return False

Testing

def test_can_win():
    s = Solution()

    assert s.canWin("++++") is True
    assert s.canWin("+") is False
    assert s.canWin("++") is True
    assert s.canWin("+++") is True
    assert s.canWin("+++++") is False
    assert s.canWin("+-++") is True
    assert s.canWin("--") is False

    print("all tests passed")

test_can_win()

Test meaning: