Java easy understand O(n^2) solution


  • 0
    X

    public class Solution {
    int[] stones;

    public boolean canCross(int[] stones) {
        this.stones = stones;
        
        return jumpTo(stones.length - 1);
    }
    
    private boolean jumpTo(int at){
        
        boolean ok = false;
        
        for(int i = at - 1; !ok && i >= 0; i--){
            int move = stones[at] - stones[i];
            ok = jumpFrom(i, move);
        }
        return ok;
    }
    
    private boolean jumpFrom(int start, int move){
        if(start == 0 && move == 1) return true;
    
        boolean ok = false;
        for(int i = start - 1; !ok && i >= 0; i--){
            int gap = Math.abs(stones[start] - stones[i] - move);
    
            if(gap <= 1){
                ok = jumpFrom(i, stones[start] - stones[i]);
            }
        }
        return ok;
    }
    

    }


Log in to reply
 

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