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