Java DP solution


  • 0
    J

    Use Set<Integer>[] to store all the steps to reach to the particular stone.

        public static boolean canCross(int[] stones) {
            if(stones[1] != 1)
                return false;
            if(stones.length == 2)
                return true;
            Set<Integer>[] dp = new Set[stones.length];
            Map<Integer, Integer> num2PosMap = new HashMap<>();
            for(int i=0; i<stones.length; i++)
                num2PosMap.put(stones[i], i);
            
            dp[1] = new HashSet<>();
            dp[1].add(1);
            for(int i=1; i<stones.length; i++) {
                if(dp[i] == null)
                    continue;
                for(int step : dp[i]) {
                    for(int ns = step - 1; ns <= step + 1; ns ++) {
                        if(ns == 0)
                            continue;
                        int target = stones[i] + ns;
                        Integer targetPos = num2PosMap.get(target);
                        if(targetPos == null)
                            continue;
                        
                        if(dp[targetPos] == null)
                            dp[targetPos] = new HashSet<>();
                        dp[targetPos].add(ns);
                        if(targetPos == dp.length-1)
                            return true;
                    }
                }
            }        
            return false;
        }```

  • 0
    D

    You forgot to check a case where stones.length==1
    Input is just [0], result should be true


Log in to reply
 

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