# Easy to understand Java solution with HashMap memorization

• The solution is easy and direct.
Recursive alogrithm with the help of hashmap, peformance is O(n^2).
When you already reached the ith, your problem will be whether you can jump from ith to the end. Now, how to figure out you can jump from ith to the end? Try to find the next position and see if you can jump from next to the end, now you can see that the problem is becoming smaller and smaller. There're possibly three 'next' position and you will try one by one, if any of them is success, then it is true, if none of works, then it is false;
This suggests a recursive algorithm, you can simply fix this by introducing a hashmap to memorize all the subproblem that previous have met.
public class Solution {
public boolean canCross(int[] stones) {
int len = stones.length;
Map<crossNode,Boolean> crossmap = new HashMap<>();
if(stones[1]!=1)
return false;
if(canCross(crossmap,stones,1,1)||canCross(crossmap,stones,1,2))
return true;
else
return false;
}
public boolean canCross(Map<crossNode,Boolean> crossmap,int[] stones,int start,int step)
{
if(start==stones.length-1)
return true;
else
{
crossNode node = new crossNode(start,step);
if(crossmap.containsKey(node))
return crossmap.get(node);
else
{
int next = findNext(stones,start,step);
if(next<0)
{
crossmap.put(node, false);
return false;
}
else
{
if(canCross(crossmap,stones,next,step)||canCross(crossmap,stones,next,step+1))
{
crossmap.put(node,true);
return true;
}
if(step>1&&canCross(crossmap,stones,next,step-1))
{
crossmap.put(node,true);
return true;
}
crossmap.put(node,false);
return false;
}
}
}
}
public int findNext(int[] stones,int start, int step)
{
int current = start;
while(current<stones.length&&stones[current]-stones[start]<step)
{
current = current+1;
}
if(current<stones.length&&stones[current]-stones[start]==step)
return current;
else
return -1;
}
private static class crossNode
{
int positions;
int steps;
public crossNode(int pos, int step)
{
this.positions = pos;
this.steps = step;
}
//override equals
public boolean equals(Object obj)
{
if((obj instanceof crossNode)&&(((crossNode)obj).positions == positions)&&(((crossNode)obj).steps == steps))
return true;
else
return false;
}
//overrides equals
public int hashCode(){
return positions;
}
}
}

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