Average 60ms Java solution, idea sharing purpose. Passed


  • 0
    A
    public class Solution {
        boolean reachable = false;//global variable to stop further action quickly
        public  boolean canCross(int[] stones) {
             Objects.requireNonNull(stones);
            reachable=false;
           
            if(stones.length==1)return true;//one stone means the one to the other side
            if(stones.length==2) return (stones[1]==1?true:false);
            //these two sets are used to reduce the loops
    //only process the one of valid position
            Set<Integer> validPositions = new HashSet<>();
            //set contains visited situation: startpoint:stepTaken
            Set<String> visited = new HashSet<String>();
            for(int i:stones){
                validPositions.add(i);
            }
            visited.add(0+":"+1);//on position 0, move one step
    
                    //starting from position 1, with 1 jump already
            dfs(visited,validPositions,1,1,stones[stones.length-1]);
            return reachable;
        }
        private  void dfs(Set<String> visited,Set<Integer> validPositions, int curPosition, int lastJump, int endPosition){
            //stop right after reached the last element
            if(reachable)return;
    
            if( curPosition+lastJump-1==endPosition
                    ||curPosition+lastJump==endPosition ||curPosition+lastJump+1==endPosition){
                reachable = true;
                return;
            }
    
            //next jump would be lastJump-1, or lastJump or lastJump+1
            for(int i=-1;i<2;i++) {
                if(!reachable) {
                    int nextPosition = curPosition + lastJump + i;
                    //frog must move forward, so jumpUnits==0 is invalid
                    if ( !visited.contains(nextPosition+":"+(lastJump+i)) && lastJump + i > 0 && validPositions.contains(nextPosition)) {
                        dfs(visited,validPositions, nextPosition, lastJump + i, endPosition);
                    }
                }
            }
            visited.add(curPosition+":"+lastJump);
            return ;
        }
    }
    

Log in to reply
 

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