Leetcode 0293 Flip Game

Problem statement

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

Solution

The idea is to check each possibility and return the result.

Complexity

Time complexity is $O(n^2)$, where $n$ is the length of state, more exact bound is $O(nk)$, where $k$ is number of possible states. Space complexity is the same.

Code

class Solution:
    def generatePossibleNextMoves(self, currentState):
        ans, n = [], len(currentState)
        for i in range(n - 1):
            if currentState[i:i+2] == "++":
                ans.append(currentState[:i] + "--" + currentState[i+2:])
        return ans