Java Iterative using HashMap with explanation


  • 0
    K

    1.Using a HashMap to store the information of each stone and its valid steps
    2.Initialize all the valid stones[i] with a HashMap
    3.When we get current steps of stones[i], we should try to check if cur_step - 1, cur_step, cur_step + 1 could reach a new stone in the HashMap. If yes, add the new step into that reached stone.
    4.Special case when i = 0 since frog could only jump 1 step.
    5.Finally we just need to check if the last stone maps to any steps.

    public class Solution {
        public boolean canCross(int[] stones) {
            Map<Integer, Set<Integer>> map = new HashMap<>();//stones[i], steps
            int[] dk = {-1,0,1};
            for(int i = 0; i < stones.length; ++i) {
                map.put(stones[i], new HashSet<Integer>());
            }
            map.get(0).add(1);
            for(int i = 0; i < stones.length; ++i) {
                for(int step: map.get(stones[i])) {
                    if (i == 0) {
                        if(map.containsKey(stones[i] + step)) map.get(stones[i] + step).add(step);
                    } else {
                        for(int k = 0; k < 3; ++k) {
                            if(step + dk[k] > 0 && map.containsKey(stones[i] + step + dk[k])) {
                                map.get(stones[i] + step + dk[k]).add(step + dk[k]);
                            }
                        }
                    }
                }
            }
            return map.get(stones[stones.length - 1]).size() != 0;
        }
    }
    

Log in to reply
 

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