220 ms O(N^2) Java with DP + HashSet.


  • 0
    I

    Here is my 220 ms O(N^2) Java solution with DP + HashSet.
    How do you guys achieve < 20s ? I tried some code posted, and got ETL.

    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length < 2) {
                return true;
            }
            int n = stones.length;
            boolean [] dp = new boolean[n];
            HashSet<Integer> [] steps = new HashSet[n];
            for (int i = 0; i < n; i++) {
                steps[i] = new HashSet<Integer>();
            }
            dp[0] = true;
            dp[1] = (stones[1] == 1 ) ? true : false;
            if (dp[1]) {
                steps[1].add(1);
            }
            for (int i = 2; i < n; i++) {
                for (int j = i - 1; stones[j] + j + 1 >= stones[i]; j--) {
                    int step = stones[i] - stones[j];
                    if (dp[j] && (steps[j].contains(step) || steps[j].contains(step - 1) || steps[j].contains(step + 1))) {
                        dp[i] = true;
                        steps[i].add(step);
                    }
                }
            }
            
            return dp[n - 1];
        }
    }
    

  • 0
    W

    @ibmtp380
    Because the test cases are different.


Log in to reply
 

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