Java 28ms DFS with memorization beats 99%


  • 0

    Using DFS to try each valid jump scheme till we can reach the end. Memorize the result for starting at stones[i] with last leap = j units in the array of dp[][];

        private HashMap<Integer, Integer> map;  //map stone number to the array indices in int[] stones
        private int end;    //the last stone
        private boolean[][] dp, visited;    //dp[i][j] is the result of starting at stones[i] given the last leap is j units
        private boolean dfs(int stone, int lastleap) {
            if (stone == end) return true;
            int index = map.get(stone);
            if (visited[index][lastleap]) return dp[index][lastleap];
            visited[index][lastleap] = true;
            for (int i = Math.max(1, lastleap-1); i <= lastleap+1; i++) {
                if (map.containsKey(stone+i) && dfs(stone+i, i)) {
                    dp[index][lastleap] = true;
                    return true;
                }
            }
            dp[index][lastleap] = false;
            return false;
        }
        public boolean canCross(int[] stones) {
            if (stones.length <= 1) return true;
            if (stones[0] != 0 || stones[1] != 1) return false;
            map = new HashMap<>();
            for (int i = 0; i < stones.length; i++) {
                if (i > 2 &&stones[i] - stones[i-1] > stones[i-1]-stones[1]+1) return false;    //if two adjacent stones are too far
                map.put(stones[i], i);
            }
            end = stones[stones.length-1];
            dp = new boolean[stones.length][stones.length];
            visited = new boolean[stones.length][stones.length];
            return dfs(1, 1);
        }
    

Log in to reply
 

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