# Super simple solution, dfs with memorization

• The idea is too simple, or sometimes naive.
Calculate the distance between each stone and compare if it matches (step - 1), step, or (step + 1).
If a match is found, dfs it. If a solution is found, return. If a failure found, record it so other routes dfs can avoid retrying the same work.

Time consumption is reasonable, beat 70%.

``````class Solution {
public boolean canCross(int[] stones) {
if (stones == null || stones.length < 2) return false;
if (stones[1] != 1) return false;
return dfs(stones, 1, 1, new HashSet<String>());
}

private boolean dfs(int[] stones, int start, int step, Set<String> set) {
if (start == stones.length - 1) {
return true;
}
if (set.contains(start + "-" + step)) return false; // Failare doomed
for (int i = start + 1; i < stones.length; i++) {
int delta = stones[i] - stones[start];

if (delta > step + 1) break;
if (delta == step - 1) {
if (dfs(stones, i, step - 1, set)) return true;
} else if (delta == step) {
if (dfs(stones, i, step, set)) return true;
} else if (delta == step + 1) {
if (dfs(stones, i, step + 1, set)) return true;
}
}
// Add the case for record
set.add(start + "-" + step);
return false;
}

}
``````

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