Straightforward MiniMax Solution


  • 0
    B

    Winner: If there exists one step(flip) I move, no matter how you move, you cannot win => I win
    Loser: No matter how I move, you can win => I lose

    public class Solution {
    public boolean canWin(String s) {
        return canWinHelper(s.toCharArray());
    }
    public boolean canWinHelper(char[] ch) {
        for(int i = 0; i < ch.length-1; i++){
            if(ch[i]=='+'&&ch[i+1]=='+'){
                //flip
                ch[i] = '-';ch[i+1]='-';
                if(cannotWin(ch)){
                    ch[i] = '+';ch[i+1]='+';
                    return true;
                }
                ch[i] = '+';ch[i+1]='+';
    
            }
        }
        return false;
    }
    public boolean cannotWin(char[] ch){
        //no matter how this move, can't win
        boolean ans = true;
        for(int i = 0; i < ch.length-1; i++){
           if(ch[i]=='+'&&ch[i+1]=='+'){
                //flip
                ch[i] = '-';ch[i+1]='-';
                ans &= canWinHelper(ch);
                ch[i] = '+';ch[i+1]='+';
            }
        } 
        return ans;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.