Java DFS + MemoTable beats 70%

• 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;
}
}``````

• 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.
}
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;
}
``````

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