JAVA 48ms commented solution by ArrayList


  • 0

    The intuitive of this problem is store every possible jump unit the frog get to a position and check if the further position could be reached.

    public class Solution {
        public boolean canCross(int[] stones) {
            if(stones == null || stones.length < 2 || stones[0] != 0 || stones[1] != 1){
                return false;
            }   // ensure the initial state to be valid;
            
            int len = stones.length;
            
            /*
            The more straightforward data structure is HashMap<Integer, List<Integer>> in which the key is the index of the position and the value is the list of jump unit the frog could be jump from former position.
            
            The reason I choose List to store the jump unit instead of HashSet is that I want to keep the order and get the maximum jump unit to limit the check if the further position could be reached.
            */
            List<List<Integer>> map = new ArrayList<List<Integer>>(len);
            
            
            for(int i = 0; i < len; i++){
                map.add(new ArrayList<Integer>());
            }
            map.get(1).add(1);
            
            for(int i = 1; i < len; i++){
                if(map.get(i).size() == 0){
                    continue;
                } 
                List<Integer> list = map.get(i);
                int max = list.get(0); // the first added jump unit must be maximum in the list.
                
                for(int j = i + 1; j < len; j++){
                    int jump = stones[j] - stones[i];
                    if(jump > max + 1){
                        break;
                    } // avoid useless check.
                    for(int k = jump - 1; k <= jump + 1; k++){
                        if(list.contains(k)){
                            map.get(j).add(jump);
                            break;
                        }
                        if(k == Integer.MAX_VALUE){
                            break; // avoid beyond the Integer boundary.
                        }
                    }
                }
            }
            
            return map.get(len - 1).size() > 0; 
        }
    }
    

Log in to reply
 

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