easy DP solution (java), can anyone improve it. Some testcases seem wrong


  • 0
    M

    map<Integer, set<Integer>>: used to record (stone pos, ith stone's all valid lastUnits to next stone)
    DP - solution: time O(n^2), space O(n)

    Rationale is: for the ith stone, check if frog can jump from any previous stone to the ith stone. use map to record the "i - [lastUnits]" pair.

    Can anyone improve this DP solution? The time to pass Leetcode test cases is 408s. Still too long time

    Another question about the test case:
    Why should [0], [0,0], [2,2] return true? Based on problem description, the stones.length must >= 2 and stones[1] - stones [ 0] should == 1. Because landed on 0th stone, frog must jump 1 unit to 1st stone. [0,0] should return false.

    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length <= 0) {
                return false;
            }
            if (stones.length == 1) {
                return true;
            }
            if (stones[1] - stones[0] != 1) {//1st jump must be 1 unit
                return false;
            }
            Map<Integer, Set<Integer>> map = new HashMap<>();
            map.put(1, new HashSet<Integer>());
            map.get(1).add(1);
    
            for (int i = 2; i < stones.length; i++) {
                for (int j = i - 1; j >= 1; j--) {
                    if (!map.containsKey(j)) {
                        continue;
                    }
                    if (!canJump(map.get(j), stones[i] - stones[j])) {
                        continue;
                    }
                    if (!map.containsKey(i)) { //can jump from jth to ith stone, record it
                        map.put(i, new HashSet<Integer>());
                    }
                    map.get(i).add(stones[i] - stones[j]);
                }
            }
            return !map.containsKey(stones.length - 1) ? false : true;
        }
        //check if can jump from jth stone to the ith stone
        private boolean canJump(Set<Integer> lastUnits, int target) {
            if (lastUnits.contains(target) || lastUnits.contains(target - 1) || lastUnits.contains(target + 1)) {
                return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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