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

  • 0

    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.

    public class Solution {
        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);
    		 //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>());
            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;
    				 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
    				 reachable = dfs(validPositions,nextPosition,lastJumpUnits+i,endPosition);
    		 return reachable;

Log in to reply

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