294. Flip Game II

Approach 1: Brute force all ways using Recursion

class Solution:
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        for i in range(len(s)-1):
            if s[i]+s[i+1] == '++' and not self.canWin(s[:i]+'--'+s[i+2:]):
                return True
        return False

This solution looks at all the possible ways any two ++'s can be replaced and continues to check using recursion if there was a way that the player cannot win. If it finds a way, then it stops and returns True, else it continues looking. If it does not find any such way to guarantee a win, it returns False

The solution is very slow since it looks at all possible ways if False, and comes in at a lowly 2.2% percentile

Time Complexity: O(1), fixed object size

Space Complexity: O(1), fixed object size