Java DFS + Memorization easy to understand


  • 0
    J

    public boolean canCross(int[] stones) {
    Map<String, Boolean> visited = new HashMap<String, Boolean>();
    return canCross(stones, 0, 1, visited);
    }

    public boolean canCross(int[] stones, int start, int jump, Map<String, Boolean> visited) {
    if (start >= stones.length) return false;
    if (start == stones.length - 1) return true;
    if (visited.containsKey(start + " + " + jump)) {
    return visited.get(start + " + " + jump);
    }

        for (int i = start + 1; i < stones.length; i++) {
            if (stones[i] == stones[start] + jump) {
                visited.put(start + " + " + jump, canCross(stones, i, jump - 1, visited) || canCross(stones, i, jump, visited) || canCross(stones, i, jump + 1, visited));
                return visited.get(start + " + " + jump);
            } 
        }
        visited.put(start + " + " + jump, false);
        return false;
    }

  • 0
    T

    tidy edition

    public boolean canCross(int[] stones) {
    
        Map<String, Boolean> visited = new HashMap<String,Boolean>();
        return canCross(stones, 0, 1, visited);
    }
    
    public boolean canCross(int[] stones, int start, int jump, Map<String, Boolean> visited) {
        if (start >= stones.length) return false;
        if (start == stones.length - 1) return true;
        if (visited.containsKey(start + " + " + jump)) {
        	return visited.get(start + " + " + jump);
        }
    
        for (int i = start + 1; i < stones.length; i++) {
        	if (stones[i] == stones[start] + jump) {
        		visited.put(start + " + " + jump, canCross(stones, i, jump - 1, visited) || canCross(stones, i, jump, visited) || canCross(stones, i, jump + 1, visited));
        			return visited.get(start + " + " + jump);
        	} 
        }
        visited.put(start + " + " + jump, false);
        return false;
    }
    

Log in to reply
 

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