# [LeetCode] 294. Flip Game II 翻转游戏 II

2021年09月15日 阅读数：1

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.html

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

For example, given `s = "++++"`, return true. The starting player can guarantee a win by flipping the middle `"++"` to become `"+--+"`.python

293. Flip Game 的拓展，此次求是否先玩者能够有一种策略必定赢游戏。post

Java:url

```public class Solution {
public boolean canWin(String s) {
for ( int i = 0; i < s.length() - 1; i ++ ){
if ( s.charAt ( i ) == '+' && s.charAt( i + 1 ) == '+' ){
StringBuilder sb = new StringBuilder ( s );
sb.setCharAt ( i , '-');
sb.setCharAt ( i + 1 ,'-');
if ( !canWin ( sb.toString() ) )
return true;
}
}
return false;
}
}```

Java: backtrackingcode

```public boolean canWin(String s) {
if(s==null||s.length()==0){
return false;
}

return canWinHelper(s.toCharArray());
}

public boolean canWinHelper(char[] arr){
for(int i=0; i<arr.length-1;i++){
if(arr[i]=='+'&&arr[i+1]=='+'){
arr[i]='-';
arr[i+1]='-';

boolean win = canWinHelper(arr);

arr[i]='+';
arr[i+1]='+';

//if there is a flip which makes the other player lose, the first play wins
if(!win){
return true;
}
}
}

return false;
}
```

Java:  DP, Time Complexity - O(2n)， Space Complexity - O(2n)htm

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

return false;
}
}　　```

Python:blog

```class Solution(object):
def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
for i in range(len(s) - 1): # 寻找全部的翻转可能
if s[i:i+2] == "++":
current = s[0:i] + "--" + s[i+2:] # 把找到的++变成--

if not self.canWin(current): # 看当前的字串是否存在边界，没有++了
return True # 对手不能赢，那就是当前翻转的赢了
return False # loop中没有返回，不能赢，当前翻转的输了　　```

C++:

```class Solution {
public:
bool canWin(string s) {
for (int i = 1; i < s.size(); ++i) {
if (s[i] == '+' && s[i - 1] == '+' && !canWin(s.substr(0, i - 1) + "--" + s.substr(i + 1))) {
return true;
}
}
return false;
}
};
```

C++:

```class Solution {
public:
bool canWin(string s) {    //朴素回溯，715MS
int len=s.size();
if(len<=1) return false;
for(int i=0;i<len-1;i++) {
string tmp=s;
if(s[i]=='+'&&s[i+1]=='+') {
tmp[i]='-';tmp[i+1]='-';
bool f=canWin(tmp);
if(!f) return true;
}
}
return false;
}
};
```

C++:

```class Solution {
public:
bool canWin(string s) {    //记录中间结果，39MS
int len=s.size();
if(len<=1) return false;
if(Memory_Map.find(s)!=Memory_Map.end()) {
return Memory_Map[s];
}
for(int i=0;i<len-1;i++) {
string tmp=s;
if(s[i]=='+'&&s[i+1]=='+') {
tmp[i]='-';tmp[i+1]='-';
bool f=canWin(tmp);
if(!f) {
Memory_Map[s]=true;
return true;
}
}
}
Memory_Map[s]=false;
return false;
}
private:
unordered_map<string,bool> Memory_Map;
};
```

[LeetCode] 293. Flip Game 翻转游戏