A better solution based on my first version, 35ms vs 60ms


  • 0
    A

    With possible movements defined as constrains/rules, and target is to find if something is reachable, a natural thought would be finding if there's a path between two nodes in a graph. So adjacency list is a good candidate data structure to use. Controversy to traditional use of adjacency list, which is built up to represent a graph before traverse it, this algorithm built it up on the fly and used it as a memoization mechanism to avoid duplicate computations. It can be changed to store real position instead of relative jump units in the list/set.

    The code is much more concise than my first version that does not have a good data structure in use.
    https://discuss.leetcode.com/topic/59906/average-60ms-java-solution-idea-sharing-purpose-passed

    public class Solution {
        public boolean canCross(int[] stones) {
            Objects.requireNonNull(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);
    		 //this is an adjacency list. and our target is to figure out 
    		 //if there's a path to a node following certain restrictions
    		 //Controversy to traditional use of adjacency list, this list is built up on the fly
            Map<Integer, Set<Integer>> validMovements = new HashMap<Integer, Set<Integer>>();
            for(int i:stones){
            	validMovements.put(i, new HashSet<Integer>());
            }
            validMovements.get(0).add(1);
            return dfs(validMovements,1,1,stones[stones.length-1]);
    	 }
    	 private boolean dfs(Map<Integer, Set<Integer>> validPositions, int curPosition, int lastJumpUnits, int endPosition){
    		 boolean reachable = false;
    		 for(int i=-1;i<=1;i++){
    			 int nextPosition = curPosition + lastJumpUnits+i;
    			 if(nextPosition==endPosition){
    				 return true;
    			 }
    			 //lastJumpUnits+i=0, not jumping, will make infinite loop so to avoid it
    			 if(lastJumpUnits+i>0 && validPositions.containsKey(nextPosition) 
    					 && !validPositions.get(nextPosition).contains(lastJumpUnits+i)){
    				 //we go here only when nextPosition is valid and nextPosition's movement has not been done
    				 //validPositions.get(nextPosition).add(lastJumpUnits+i);
    				 reachable = dfs(validPositions,nextPosition,lastJumpUnits+i,endPosition);
    				 if(reachable)break;
    			 }
    		 }
    		 validPositions.get(curPosition).add(lastJumpUnits);
    		 return reachable;
    	 }
    }
    

Log in to reply
 

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