Java solution easy to understand using DFS and Memorization


  • 0
    C
    public boolean canCross(int[] stones) {
    		Map<Integer, Integer> stonePosMap = new HashMap<Integer, Integer>();
    
    		// used to find it next possible jump will land on a stone or water
    		for (int i = 0; i < stones.length; i++) {
    			stonePosMap.put(stones[i], i);
    		}
    
    		return dfs(stones, 0, 0, stonePosMap, new HashSet<String>());
    	}
    
    	private boolean dfs(int[] stones, int idx, int prevJump, Map<Integer, Integer> stonePosMap,
    			Set<String> visitedPath) {
    		// represents when we have landed on the last stone
    		if (idx == stones.length - 1) {
    			return true;
    		}
    
    		// creating path information
    		String path = new StringBuilder().append("from: ").append(idx).append(" with Jump: ").append(prevJump)
    				.toString();
    
    		// in this memorization technique we are storing all the failed path.
    		if (visitedPath.contains(path)) {
    			return false;
    		}
    
    		// this tries all the possible k-1, k and k+1 jumps
    		for (int i = -1; i <= 1; i++) {
    			Integer nextIdx = stonePosMap.get(stones[idx] + i + prevJump);
    
    			// next possible jump should have a stone and should be in the
    			// forward direction
    			if (nextIdx != null && nextIdx > idx) {
    				if (dfs(stones, nextIdx, i + prevJump, stonePosMap, visitedPath)) {
    					return true;
    				}
    			}
    		}
    
    		// used for memorization so that we dont compute the visited path again
    		visitedPath.add(path);
    		return false;
    	}
    

Log in to reply
 

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