Java Solution BackTracking, Dynamic Programming


  • 0
    static int[] jumpOffset = {1,0,-1};
    
    public boolean canCross(int[] stones) {
    	if(stones.length>1 && stones[1]!=1) return false;
    	Map<Integer,List<Integer>> visitedWithKJump = new HashMap<>();
    	return canCrossBackTrack(stones,1,1, visitedWithKJump);
    }
    
    public boolean canCrossBackTrack(int[] stones, int currentPosition, int lastJumpSize, Map<Integer,List<Integer>> visited) {
    	if(visited.keySet().contains(currentPosition) && visited.get(currentPosition).contains(lastJumpSize)) return false;
    	if(visited.containsKey(currentPosition)) {
    		visited.get(currentPosition).add(lastJumpSize);
    	} else {
    		List<Integer> kJumpsInThisPosition = new ArrayList<>();
    		kJumpsInThisPosition.add(lastJumpSize);
    		visited.put(currentPosition, kJumpsInThisPosition);
    	}
    	if(currentPosition==stones.length-1) return true;
    	if(currentPosition>stones.length-1) return false;
    	if(stones[currentPosition+1]>stones[currentPosition]+lastJumpSize+1) return false;
    	if(stones[stones.length-1]<stones[currentPosition]+lastJumpSize-1) return false;
    	for(int offset: jumpOffset) {
    		int nextJump = lastJumpSize+offset;
    		int nextJumpValue = stones[currentPosition]+nextJump;
    		int nextPosition = Arrays.binarySearch(stones, currentPosition+1, stones.length, nextJumpValue);
    		if(nextPosition>currentPosition) {
    			if(canCrossBackTrack(stones, nextPosition, nextJump, visited)) {
    				return true;
    			}
    		}
    	}
    	return false;
    }
    

Log in to reply
 

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