# 【LEETCODE】模拟面试-294.Flip Game II

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 twoconsecutive "++" 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.

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

input: a string with only `+ and -` two kinds of characters output: for a given input, based on the game rule, return whether there is one strategy that can make the first player win, if yes, return true, if there is none, return false corner: when the string if null, return false

We will first change the string to a character array.

And apply `Backtracking` algorithm to solve it.

The starting point of the first player will iterate from `0 to arr.length - 2`, when he finds two consecutive `++`, he will soon change it into `--`.

Then the second player will do the same thing, so we pass current changed array to the second player, and he will receive a result: `boolean otherWin = helper(arr);`

If the second player will win, means he will return a `true` to upper level, the first player should recover his current strategy by change the `--` to original `++`, and keep moving `i` to next step, so that he can find other strategy that will make himself finally win the game, as long as there is just one strategy make it happen, the final result will be true, otherwise, it will be false.

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

return helper(s.toCharArray());
}

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

boolean otherWin = helper(arr);         //2人轮流

arr[i] = '+';               //返回到upper level后恢复＋号
arr[i + 1] = '+';

if ( !otherWin ){           //另一人false时走这一步，另一人true时，要继续遍历＋＋对
return true;            //直到找到某一种走法可以让另一人false，最终整体返回的值为true，此时第一人赢
}
}
}

return false;           //如果遍历到头没有＋＋对了，而且几种走法都一直找不到赢的走法了，第一人就最终false
}
}```

280 篇文章46 人订阅

0 条评论

## 相关文章

### 厕读：每日一题，面试无忧

2. 下面关于java.lang.Exception类的说法正确的是（） A 继承自Throwable B Serialable CD 不记...

36350

### 程序员面试闪充--Block

1、介绍 Block是OC中非常重要的一种技术手段 ? 2、从c函数和oc函数的区别来定义block C函数写法：int add(int num1, int n...

29880

8510

30640

10210

85970

11240

31850

16720

15920