Regular java BFS solution and 2-end BFS solution with improvement


  • 4
    Y

    Basic solution, runtime: 260ms

    class Solution {
        public int openLock(String[] deadends, String target) {
            Queue<String> q = new LinkedList<>();
            Set<String> deads = new HashSet<>(Arrays.asList(deadends));
            Set<String> visited = new HashSet<>();
            q.offer("0000");
            visited.add("0000");
            int level = 0;
            while(!q.isEmpty()) {
                int size = q.size();
                while(size > 0) {
                    String s = q.poll();
                    if(deads.contains(s)) {
                        size --;
                        continue;
                    }
                    if(s.equals(target)) return level;
                    StringBuilder sb = new StringBuilder(s);
                    for(int i = 0; i < 4; i ++) {
                        char c = sb.charAt(i);
                        String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1);
                        String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1);
                        if(!visited.contains(s1) && !deads.contains(s1)) {
                            q.offer(s1);
                            visited.add(s1);
                        }
                        if(!visited.contains(s2) && !deads.contains(s2)) {
                            q.offer(s2);
                            visited.add(s2);
                        }
                    }
                    size --;
                }
                level ++;
            }
            return -1;
        }
    }
    

    Regular 2 - end solution, runtime: 85ms

    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> begin = new HashSet<>();
            Set<String> end = new HashSet<>();
            Set<String> deads = new HashSet<>(Arrays.asList(deadends));
            begin.add("0000");
            end.add(target);
            int level = 0;
            while(!begin.isEmpty() && !end.isEmpty()) {
                Set<String> temp = new HashSet<>();
                for(String s : begin) {
                    if(end.contains(s)) return level;
                    if(deads.contains(s)) continue;
                    deads.add(s);
                    StringBuilder sb = new StringBuilder(s);
                    for(int i = 0; i < 4; i ++) {
                        char c = sb.charAt(i);
                        String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1);
                        String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1);
                        if(!deads.contains(s1))
                            temp.add(s1);
                        if(!deads.contains(s2))
                            temp.add(s2);
                    }
                }
                level ++;
                begin = end;
                end = temp;
            }
            return -1;
        }
    }
    

    You can still improve this 2-end solution, by adding:

    if (begin.size() > end.size()) {
        temp = begin;
        begin = end;
        end = temp;
    }
    

    By always picking a smaller set, this process could reduce a little(since in this problem the scale on both sides are similar) time complexity and memory complexity. Here's the full version, runtime: 80ms

    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> begin = new HashSet<>();
            Set<String> end = new HashSet<>();
            Set<String> deads = new HashSet<>(Arrays.asList(deadends));
            begin.add("0000");
            end.add(target);
            int level = 0;
            Set<String> temp;
            while(!begin.isEmpty() && !end.isEmpty()) {
                if (begin.size() > end.size()) {
                    temp = begin;
                    begin = end;
                    end = temp;
                }
                temp = new HashSet<>();
                for(String s : begin) {
                    if(end.contains(s)) return level;
                    if(deads.contains(s)) continue;
                    deads.add(s);
                    StringBuilder sb = new StringBuilder(s);
                    for(int i = 0; i < 4; i ++) {
                        char c = sb.charAt(i);
                        String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1);
                        String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1);
                        if(!deads.contains(s1))
                            temp.add(s1);
                        if(!deads.contains(s2))
                            temp.add(s2);
                    }
                }
                level ++;
                begin = temp;
            }
            return -1;
        }
    }
    

  • 0
    B

    Great solution.

    And could you please explain what is the purpose of those codes below?

    begin = end;
    end = temp;
    

    Or could you provide a link talking about 2-end BFS? thanks. :)


  • 1
    Y

    @biaoge The purpose of doing this is to exchange 'begin' and 'end'. After running the code, we will be processing BFS for the elements from 'end' set in the next loop. The whole process is like:
    Running BFS in 'begin' set -----> Create a new set 'temp' to store the value -----> begin = temp -----> 'begin'(is 'temp' now) and 'end' exchange value ------> (next loop) Running BFS in 'end'(is now 'begin') .....

    I don't think you really need any reference to learn about 2 - end BFS. It's basically a slight transform of the regular BFS. If you know exactly the start position and the end position(In this problem, the start position is "0000" and the end position is target), you can do BFS from both side instead of doing BFS only from the starting position.You find the intersection, you get the result. Otherwise, if you do not know what the end point is, you can't use 2 - end BFS (eg. maze problem, as you wouldn't be able to know the exit postion).
    The graph below is pretty straightforward, hope it helps!

    0_1514356630112_6635898ag9ca387a4da4f&690.png


  • 0
    H

    @biaoge It means not only does "0000" moves towards target; target also moves towards "0000". Eventually they meet mid-way.
    Reason why it is faster is - in each move, we create ourselves 8 branches. As"0000" moves along, the tmp set grows exponentially (8^level). Whereas if we have 2 ends moving, the exponent can be reduced to half. Therefore reducing our search time.


  • 0
    This post is deleted!

  • 0
    public int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        Set<String> visited = new HashSet<>();
        q.offer("0000");
        visited.add("0000");
        int level = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            for(int n = 0; n < size; n++) {
                String s = q.poll();
                if(deads.contains(s)) continue;
                if(s.equals(target)) return level;
    
                for(int i = 0; i < 4; i++) { // all 4 positions, go one number above, one below
                    char c = s.charAt(i);
                    String prefix = s.substring(0, i), postfix = s.substring(i + 1);
                    addToQueue(q, getNextValue(s, c, prefix, postfix, true), visited, deads);
                    addToQueue(q, getNextValue(s, c, prefix, postfix, false), visited, deads);
                }
            }
            level ++;
        }
        return -1;
    }
    
    private String getNextValue(String s, char c, String prefix, String postfix, boolean previous) {
        if(previous) return  prefix + (c == '9' ? 0 : c - '0' + 1) + postfix;
        return prefix + (c == '0' ? 9 : c - '0' - 1) + postfix;
    }
    private void addToQueue(Queue<String> q, String str, Set<String> visited, Set<String> deads) {
        if(!visited.contains(str) && !deads.contains(str)) {
            q.offer(str);
            visited.add(str);
        }
    }

Log in to reply
 

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