Simple and easy understand java solution


  • 2
    F
    public boolean canCross(int[] stones) {
            if (stones == null || stones.length == 0) {
                return false;
            }
            if (stones[1] > 1) {
                return false;
            }
    
            Set[] lastJump = new Set[stones.length];
            for (int i = 1; i < stones.length; i++) {
                lastJump[i] = new HashSet<Integer>();
            }
            lastJump[1].add(1);
            
            for (int i = 2; i < stones.length; i++) {
                for (int j = 1; j < i; j++) {
                    //cell j can be reached
                    if (lastJump[j].size() > 0) {
                        int currJump = stones[i] - stones[j];
                        if (lastJump[j].contains(currJump) || 
                            lastJump[j].contains(currJump + 1) ||
                            lastJump[j].contains(currJump - 1)) {
                            lastJump[i].add(currJump);
                        }
                    }
                }
            }
            return lastJump[stones.length - 1].size() > 0;
        }
    

Log in to reply
 

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