Java DFS with memorization. Easy to understand


  • 0
    C
    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length == 0) {
                return true;
            }
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < stones.length; i++) {
                set.add(stones[i]);
            }
            Map<String, Boolean> cache = new HashMap<>();
            return dfs(stones, 0, 1, set, cache);
        }
        
        private boolean dfs(int[] stones, int index, int jump, Set<Integer> set, Map<String, Boolean> cache) {
            if (index == stones[stones.length - 1]) {
                return true;
            }
            if (jump <= 0 || !set.contains(index)) {
                return false;
            }
            String encode = index + "->" + jump;
            if (cache.containsKey(encode)) {
                return cache.get(encode);
            }
            boolean res = dfs(stones, index + jump, jump - 1, set, cache) ||
                          dfs(stones, index + jump, jump, set, cache)     ||
                          dfs(stones, index + jump, jump + 1, set, cache);
            cache.put(encode, res);
            return res;
        }
    }
    

Log in to reply
 

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