A better solution based on my first version, 35ms vs 60ms

• With possible movements defined as constrains/rules, and target is to find if something is reachable, a natural thought would be finding if there's a path between two nodes in a graph. So adjacency list is a good candidate data structure to use. Controversy to traditional use of adjacency list, which is built up to represent a graph before traverse it, this algorithm built it up on the fly and used it as a memoization mechanism to avoid duplicate computations. It can be changed to store real position instead of relative jump units in the list/set.

The code is much more concise than my first version that does not have a good data structure in use.
https://discuss.leetcode.com/topic/59906/average-60ms-java-solution-idea-sharing-purpose-passed

``````public class Solution {
public boolean canCross(int[] stones) {
Objects.requireNonNull(stones);
if(stones.length==1)return true;//one stone means the one to the other side
if(stones.length==2) return (stones[1]==1?true:false);
//this is an adjacency list. and our target is to figure out
//if there's a path to a node following certain restrictions
//Controversy to traditional use of adjacency list, this list is built up on the fly
Map<Integer, Set<Integer>> validMovements = new HashMap<Integer, Set<Integer>>();
for(int i:stones){
validMovements.put(i, new HashSet<Integer>());
}
return dfs(validMovements,1,1,stones[stones.length-1]);
}
private boolean dfs(Map<Integer, Set<Integer>> validPositions, int curPosition, int lastJumpUnits, int endPosition){
boolean reachable = false;
for(int i=-1;i<=1;i++){
int nextPosition = curPosition + lastJumpUnits+i;
if(nextPosition==endPosition){
return true;
}
//lastJumpUnits+i=0, not jumping, will make infinite loop so to avoid it
if(lastJumpUnits+i>0 && validPositions.containsKey(nextPosition)
&& !validPositions.get(nextPosition).contains(lastJumpUnits+i)){
//we go here only when nextPosition is valid and nextPosition's movement has not been done