Java DFS with memorization and some math for early termination (19ms)


  • 0

    Similar idea with other DFS solution by going from the first one to the last.
    From the observation, I found that there are lower bound and upper bound from stone 1 to stone n of n steps. The minimum steps is Max(n, k-1) and the maximum steps is (k+1)+(k+2)+(k+3)+....+(k+n).
    Therefore, if the value of last stone is less than minimum steps or greater than maximum steps, we know that there is no way to reach it from current stone.
    For example, with the case of [0,1,3,6,10,11, 100]
    when from = 0, to = 6 which has stones[0] = 0, stones[6]=100, and k=1
    also, len = 6-0=6.
    Therefore, the maximum steps from 0 to 6 with k = 1 is 1+2+3+4+5+6 = 21 and
    maximum stone value is 0+21=21. Since stones[6]=100, it is impossible to jump from stone 0 to stone 6 when k=1.
    On the other hand, when from = 4, to = 5 which has stones[4] = 10, stones[5]=11, and k=4, also, len = 5-4=1.
    Therefore, the minimum steps from 4 to 5 with k = 4 is Max(1,4-1) = 3 and
    minimum stone value is 10+3=13. Since stones[5]=11, it is impossible to jump from stone 4 to stone 5 when k=4.

    public class Solution {
        Map<Integer, Integer> map = new HashMap<>();
        Set<String> mem = new HashSet<>();
        int to;
        int goal;
        boolean dfs(int from, int k, int[] stones){
            if (from == to) return true;
            int cur = stones[from];
            int len = to-from;
            String key = ""+from +":"+k;
            if ( mem.contains(key) ) return false;
            if ( (goal > cur + ( (k+1+k+len)*len )/2) || (goal < cur + Math.max(len, k-1)) ) {
                mem.add(key);
                return false;
            }
            for (int next=k+1; next >=k-1; next--) {
                if ( (next >= 1) && map.containsKey(cur+next) ) {
                    if ( dfs( map.get(cur+next), next, stones) ) return true;
                }
            }
            mem.add(key);
            return false;
        }
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length <=1) return true;
            to = stones.length-1;
            goal = stones[to];
            for (int i=1; i <= to; i++) { 
                map.put(stones[i], i);
            }
            return dfs( 0, 0, stones);
        }
    }
    

  • 0

    Another DFS version incorporating the math to find the range. (18ms)

    public class Solution {
        Set<String> mem = new HashSet<>();
        int to;
        int goal;
        boolean dfs(int from, int k, int[] stones){
            int cur = stones[from];
            int len = to-from;
            String key = ""+from +":"+k;
            if ( mem.contains(key) ) return false;
            if ( goal >= cur+k-1 && goal <= cur+k+1) return true;
            int min = cur + Math.max(len, k);
            int max = cur + ( (k+1+k+len)*len )/2;
            if (len > 1 && goal <= max && goal >= min ) {
                for (int i=from+1; i<=to-1; i++) {
                    int next = stones[i]-cur;
                    if ( next >= k-1 && next <= k+1) {
                        if ( dfs( i, next, stones) ) {
                            return true;
                        }
                    }
                }
            }
            mem.add(key);
            return false;
        }
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length <=1) return true;
            to = stones.length-1;
            goal = stones[to];
            return dfs( 0, 0, stones);
        }
    }
    

Log in to reply
 

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