# 294. Flip Game II

### Approach 1: Brute force all ways using Recursion

```python
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*