AC JAVA Solution using 2-end BFS


  • 1
    J

    Each time we work with a smaller-sized set by checking the set from "0000" end and from target end (to save time).
    At any instance, if either set is empty, it means we hit a dead end. So return -1.
    If we match a password from the other end, we find the solution. So return counter at that moment.
    Note: if you have encountered the 38/40 wrong answer problem, just check whether "0000" is in your deadends. This should solve the problem.

    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> dds = new HashSet<>();
            for (int i = 0; i < deadends.length; i++) dds.add(deadends[i]);
            if (dds.contains("0000")) return -1;
            Set<String> start = new HashSet<>();
            start.add("0000");
            Set<String> end = new HashSet<>();
            end.add(target);
            Set<String> visited = new HashSet<>();
            visited.add("0000");
            visited.add(target);
            int counter = 0;
            while (!start.isEmpty() && !end.isEmpty()) {
                counter++;
                if (start.size() > end.size()) {
                    Set<String> temp = start;
                    start = end; 
                    end = temp;
                }
                Set<String> temp_start = new HashSet<>();
                for (String s : start) {
                    for (int i = 0; i < 4; i++) {
                        char[] s1_arr = s.toCharArray();
                        char[] s2_arr = s.toCharArray();
                        s1_arr[i]++;
                        s2_arr[i]--;
                        if (s1_arr[i] > '9') s1_arr[i] -= 10;
                        if (s2_arr[i] < '0') s2_arr[i] += 10;
                        String s1 = String.valueOf(s1_arr);
                        String s2 = String.valueOf(s2_arr);
                        if (end.contains(s1) || end.contains(s2)) return counter;
                        if (!dds.contains(s1) && !visited.contains(s1)) {
                            visited.add(s1);
                            temp_start.add(s1);
                        }
                        if (!dds.contains(s2) && !visited.contains(s2)) {
                            visited.add(s2);
                            temp_start.add(s2);
                        }
                    }
                }
                start = temp_start;
            }
            return -1;
        }
    }
    

Log in to reply
 

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