Java 24ms recrusive solution


  • 0
    J

    basic idea is to use a boolean matrix to save intermediate result. initially used 2-D array, but seems hashmap perform better.

    dp[i] is a hash map, which stores if it's possible to reach from stone 0 to i with possible final steps. so it dp[i].get(k) == true means it's possible to reach stone i and the final step jumps k units.

      public boolean canCross(int[] stones) {
        int n = stones.length;
        if (n <= 1) return true;
        if (n == 2) return stones[1] == 1;
        Map<Integer, Integer> indexs = new HashMap<>();
        for (int i = 0; i < n; i++) indexs.put(stones[i], i);
        HashMap<Integer, Boolean>[] dp = new HashMap[n];
        dp[0] = new HashMap<>();
        dp[0].put(0, true);
        dp[1] = new HashMap<>();
        dp[1].put(1, true);
        for (int i = n - 1 ; i >= 0; i--) {
          if (canReach(stones, indexs, n - 1, stones[n - 1] - stones[i], dp)) return true;
        }
        return false;
      }
    
      private boolean canReach(int[] stones, Map<Integer, Integer> indexs, int end, int steps, HashMap<Integer, Boolean>[] dp) {
        dp[end] = (dp[end] == null ? new HashMap<>() : dp[end]);
        Boolean result = dp[end].get(steps);
        if (result == null) {
          Integer index = indexs.get(stones[end] - steps);
          result = false;
          if (index != null) {
            for (int i = -1; i <= 1; i++) {
              if ((steps + i) > 0 && canReach(stones, indexs, index, steps + i, dp)) {
                result = true;
                break;
              }
            }
          }
          dp[end].put(steps, result);
        }
        return result;
      }
    

Log in to reply
 

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