Simple self explanatory solution using memoization


  • 0
    S
    public class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer,Integer> stoneIndex = new HashMap<Integer,Integer>();
        Set<String> dp = new HashSet<String>();
        for(int i=0;i<stones.length;i++)
            stoneIndex.put(stones[i],i);
        return canCross(stones,0,0,stoneIndex,dp);
    }
    
    boolean canCross(int[] stones,int index,int k,Map<Integer,Integer> stoneIndex,Set<String> dp) {
        if(index == stones.length-1)
            return true;
        if(dp.contains(index+""+k))
            return false;
        if(stones[index] != 0 && k!=1 &&  stoneIndex.containsKey(stones[index] + k-1)) {
            if(canCross(stones,stoneIndex.get(stones[index] + k-1),k-1,stoneIndex,dp))
                return true;
        }
        if(k>=1 && stoneIndex.containsKey(stones[index] + k)) {
            if(canCross(stones,stoneIndex.get(stones[index] + k),k,stoneIndex,dp))
                return true;
        }
        if(stoneIndex.containsKey(stones[index] + k+1)) {
            if(canCross(stones,stoneIndex.get(stones[index] + k+1),k+1,stoneIndex,dp))
                return true;
        }
        dp.add(index+""+k);
        return false;
    }
    }

Log in to reply
 

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