traditional mind . java dp + memo , beats 85 %


  • 0
    2
    public class Solution {
        public boolean canCross(int[] stones) {
            if(stones == null || stones.length < 2 || stones[1] - stones[0] > 1) {
                return false;
            }
            int k = 1;
            int idx = 0;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int i = 0; i < stones.length; i++) {
                map.put(stones[i], i);
            }
            int[][] memo = new int[stones.length][stones[stones.length - 1] > 1100 ? 1100 : stones[stones.length - 1] + 1 ];
            return help(stones, 0, 1, map, memo);
            
        }
        private boolean help(int[] nums, int idx, int k, Map<Integer, Integer> map, int[][] memo) {
            if(memo[idx][k] != 0) {
                return memo[idx][k] == 1 ? true : false;
            }
            if(idx == nums.length -1 || nums[idx] + k + 1 == nums[nums.length - 1]) {
                memo[idx][k] = 1;
                return true;
            }
            if(map.containsKey(nums[idx] + k + 1)) {
                if(help(nums, map.get(nums[idx] + k + 1),k + 1, map, memo)) {
                    memo[idx][k] = 1;
                    return true;
                }else {
                    memo[idx][k] = 2;
                }
            } 
            if(map.containsKey(nums[idx] + k)) {
                if(help(nums, map.get(nums[idx] + k),k, map, memo)) {
                    memo[idx][k] = 1;
                    return true;
                }else {
                    memo[idx][k] = 2;
                }
            }
            if(k - 1 > 0 && map.containsKey(nums[idx] + k - 1)) {
                if(help(nums, map.get(nums[idx] + k - 1),k - 1, map, memo)) {
                    memo[idx][k] = 1;
                    return true;
                }else {
                    memo[idx][k] = 2;
                } 
            }   
                
            memo[idx][k] = 2;
            return false;
        
      }
    }
    

Log in to reply
 

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