My Java AC solution --backtracking -- 37ms


  • 0
    S
    public class Solution {
        public boolean canWin(String s) {
            //remember bits flipped
            int[] visited = new int[s.length()];
            //mark existing - to 1
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='-'){
                    visited[i]=1;
                }
            }
            return canWinR(s,1,visited);
        }
        
        public boolean canWinR(String s, int step, int[] visited){
            //first player's turn
            if(step%2==1){
                for(int i=0;i<s.length()-1;i++)
                {
                    //if already flipped, skip
                    if(visited[i]==1||visited[i+1]==1) continue;
                    //mark the two to be flipped
                        visited[i]=1;
                        visited[i+1]=1;
                        //if this move can win, return;
                        boolean r=canWinR(s,step+1,visited);
                        visited[i]=0;
                        visited[i+1]=0;
                        if(r) return true;
                }
                return false;
                
            } else {
                //second player's turn. 
                //all second player's moves should result in first player to win
                //otherwise, first player cannot be guaranteed to win
                for(int i=0;i<s.length()-1;i++)
                {
                    if(visited[i]==1||visited[i+1]==1) continue;
                        visited[i]=1;
                        visited[i+1]=1;
                        boolean r = canWinR(s,step+1,visited);
                        visited[i]=0;
                        visited[i+1]=0;
                        //this move leads to first player to lose , return false;
                        if(!r) return false;
                }
                return true;
            }
        }
    }
    

Log in to reply
 

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