Slow but intuitive method using map which stores the previous steps


  • 1
    G

    This is the method :

    public boolean canCross(int[] stones) {
        int len = stones[stones.length-1];
        if(len == 0) return true;
        Map<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        map.put(1, new HashSet<Integer>());
        map.get(1).add(1);
        for(int i : stones) {
            if(i == 0) continue;
            if(!map.containsKey(i)) continue;
            for(int step: map.get(i)) {
                if(step > 1) {
                    int min = step - 1;
                    if(!map.containsKey(i+min)) map.put(i+min, new HashSet<Integer>());
                    map.get(i+min).add(min);
                }
                if(!map.containsKey(i+step)) map.put(i+step, new HashSet<Integer>());
                map.get(i+step).add(step);
                int max = step + 1;
                if(!map.containsKey(i+max)) map.put(i+max, new HashSet<Integer>());
                map.get(i+max).add(max);
            }
        }
        return map.containsKey(len) && map.get(len).size() > 0 ;
    }

  • 0
    L

    6666666666666666666


  • 0
    G

    @li.jiawei 555555


Log in to reply
 

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