# 294. Flip Game II

## Problem

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example:

```
Input: s = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".
```

Follow up: Derive your algorithm’s runtime complexity.

## Code

```
class Solution {
public boolean canWin(String s) {
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) == '+' && s.charAt(i - 1) == '+'){
char[] arr = s.toCharArray();
arr[i] = '-';
arr[i - 1] = '-';
if(!canWin(new String(arr))){
return true;
}
}
}
return false;
}
}
```

```
class Solution:
def canWin(self, s: str) -> bool:
for i in range(len(s) - 1):
if s[i] == '+' and s[i + 1] == '+':
# 对手不能赢的情况下
if not self.canWin(s[:i] + "--" + s[i + 2:]):
return True
# 没有能赢的情况
return False
```

按 <- 键看上一题！
293. Flip Game

按 -> 键看下一题！
295. Find Median from Data Stream