Java DFS + MemoTable beats 70%


  • 0
    S

    Basic idea is DFS + Memo Table, Each time I save the DFS result of "stone + step" info to a Map

    public class Solution {
        public boolean canCross(int[] stones) {
            Set<Integer> set = new HashSet<>();
            Map<String, Boolean> map = new HashMap<>();
            for(int stone : stones) set.add(stone);
            if(stones[0] + 1 != stones[1]) return false;
            
            return dfs(stones[1], 1, set, map, stones[stones.length - 1]);
        }
        
        public boolean dfs(int stone, int step, Set<Integer> set, Map<String, Boolean> map, int target) {
            if(map.containsKey(stone + "x" + step)) {
                return map.get(stone + "x" + step);
            }
            if(step <= 0 || !set.contains(stone)) return false;
            if(stone == target) {
                map.put(stone + "x" + step, true);
                return true;
            }
    
            boolean search = dfs(stone + step, step, set, map, target) 
                || dfs(stone + step + 1, step + 1, set, map, target) 
                || dfs(stone + step - 1, step - 1, set, map, target); 
            map.put(stone + "x" + step, search);
            return search;
        }    
    }

  • 0

    My solution is attached. Memorization seems a good optimization. However, this solution can beat 95% somehow.

        public boolean canCross(int[] stones) {
            if (stones == null || stones.length == 0) {return false;}
            int n = stones.length;
            if (n == 1) {return true;}
            if (stones[1] != 1) {return false;}
            if (n == 2) {return true;}
            int last = stones[n - 1];
            HashSet<Integer> hs = new HashSet();
            for (int i = 0; i < n; i++) {
                if (i > 3 && stones[i] > stones[i - 1] * 2) {return false;} // The two stones are too far away. 
                hs.add(stones[i]);
            }
            return canReach(hs, last, 1, 1);
        }
        
        private boolean canReach(HashSet<Integer> hs, int last, int pos, int jump) {
            if (pos + jump - 1 == last || pos + jump == last || pos + jump + 1 == last) {
                return true;
            }
            if ((hs.contains(pos + jump + 1) && canReach(hs, last, pos + jump + 1, jump + 1))
               || (hs.contains(pos + jump) && canReach(hs, last, pos + jump, jump))
               || (jump > 1 && hs.contains(pos + jump - 1) && canReach(hs, last, pos + jump - 1, jump - 1))) {
                return true;
            }
            return false;
        }
    

Log in to reply
 

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