Easy to understand Java solution with HashMap memorization


  • 0
    H

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


Log in to reply
 

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