regular BFS and two-end BFS


  • 0

    Java using regular BFS: 230 ~ 350ms
    Java using two-end BFS: 60 ~ 90ms

    //regular BFS
    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> set = new HashSet<>(Arrays.asList(deadends));
            if (set.contains("0000")) return -1;
            
            Queue<String> q = new LinkedList<>();
            Set<String> visited = new HashSet<>();
            visited.add("0000");
            q.offer("0000");
            
            int step = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    String curr = q.poll();
                    for (int j = 0; j < 4; j++) {
                        String plus1 = curr.substring(0, j) + (curr.charAt(j) == '9' ? 0 : curr.charAt(j) - '0' + 1) + curr.substring(j + 1);
                        String minus1 = curr.substring(0, j) + (curr.charAt(j) == '0' ? 9 : curr.charAt(j) - '0' - 1) + curr.substring(j + 1);
                        if (!set.contains(plus1) && !visited.contains(plus1)) {
                            visited.add(plus1);
                            q.offer(plus1);
                        }
                        if (!set.contains(minus1) && !visited.contains(minus1)) {
                            visited.add(minus1);
                            q.offer(minus1);
                        }
                        if (plus1.equals(target) || minus1.equals(target)) return step + 1;
                    }
                }
                step++;
            }
            return -1;
        }
    }
    
    // two-end BFS
    class Solution {
        public int openLock(String[] deadends, String target) {
            HashSet<String> set = new HashSet<>(Arrays.asList(deadends));
            if (set.contains("0000") || set.contains(target)) return -1;
            Set<String> beginSet = new HashSet<>();
            Set<String> endSet = new HashSet<>();
            beginSet.add("0000");
            endSet.add(target);
            Set<String> visited = new HashSet<>();
            visited.add("0000");
            
            int step = 0;
            Set<String> temp = new HashSet<>();
            while (!beginSet.isEmpty() && !endSet.isEmpty()) {
                if (beginSet.size() > endSet.size()) {
                    temp = beginSet;
                    beginSet = endSet;
                    endSet = temp;
                }
                temp = new HashSet<>();
                for (String s : beginSet) {
                    for (int i = 0; i < 4; i++) {
                        String plus1 = s.substring(0, i) + (s.charAt(i) == '9' ? 0 : s.charAt(i) - '0' + 1) + s.substring(i + 1);
                        String minus1 = s.substring(0, i) + (s.charAt(i) == '0' ? 9 : s.charAt(i) - '0' - 1) + s.substring(i + 1);
                        if (endSet.contains(plus1) || endSet.contains(minus1)) return step + 1;
                        if (!visited.contains(plus1) && !set.contains(plus1)) {
                            temp.add(plus1);
                            visited.add(plus1);
                        }
                        if (!visited.contains(minus1) && !set.contains(minus1)) {
                            temp.add(minus1);
                            visited.add(minus1);
                        }
                    }
                }
                beginSet = temp;
                step++;
            }
            return -1;
        }
    }
    

Log in to reply
 

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