Average 60ms Java solution, idea sharing purpose. Passed

  • 0
    public class Solution {
        boolean reachable = false;//global variable to stop further action quickly
        public  boolean canCross(int[] stones) {
            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){
            visited.add(0+":"+1);//on position 0, move one step
                    //starting from position 1, with 1 jump already
            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( curPosition+lastJump-1==endPosition
                    ||curPosition+lastJump==endPosition ||curPosition+lastJump+1==endPosition){
                reachable = true;
            //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);
            return ;

Log in to reply

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