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

Follow up: Derive your algorithm's runtime complexity.

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
    }
}