Java 7ms recursion Solution with explaination, easy to understand


  • 3
    Y
    public class Solution {
        public boolean PredictTheWinner(int[] nums) {
            if(nums.length <= 1){
                return true;
            }
            return canWin(nums, 0, nums.length-1, 0, 0);
        }
        private boolean canWin(int[] nums, int left, int right, int fistScore, int secondScore){
            // assume fistScore is the score of current player (to pick in this round)
            if(left > right){
                return fistScore >= secondScore;
            }
            fistScore += nums[left++]; //  pick left
            if(!canWin(nums, left, right, secondScore, fistScore)){ 
            // check if next player can win. if next player cannot win, return true, which means the current player can win 
                return true;
            }
            // backtrack
            left--;
            fistScore -= nums[left];
            // pick right;
            fistScore += nums[right--];
            if(!canWin(nums, left, right, secondScore, fistScore)){
            //check if next player can win
                return true;
            }
            right++;
            fistScore -= nums[right];
            return false;
        }
    }
    

Log in to reply
 

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