Problem statement

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

Solution

Let us use problem 0293 Flip Game to generate all possible positions. We need to do recursion here: let is1Win(state) be a function if first can win, starting with string state It is True, if we have at least one False for possible moves state_1, ... state_k. And it is False, if for all moves it is True.

Complexity

To evaluate complexity we need to solve recurrent: $T(n) = T(0)\cdot T(n-2) + T(1)\cdot T(n-3) + \dots T(n-2) \cdot T(0)$, which is similar to Catalan numbers recursion $C_n \approx 4^n / n^{3/2}$.

Code

class Solution:
    def canWin(self, currentState):
        def moves(state):
            ans, n = [], len(state)
            for i in range(n - 1):
                if state[i:i+2] == "++":
                    ans.append(state[:i] + "--" + state[i+2:])
            return ans
        
        @lru_cache(None)
        def is1Win(state):
            for neib in moves(state):
                if not is1Win(neib): return True
            return False
        
        return is1Win(currentState)

Remark

I think it can be solved in $O(n)$, using Sprague-Grundy theorem.