30ms BFS solution in Java


  • 0
    public int openLock(String[] deadends, String target) {
        boolean[] dead = new boolean[10000];
        for(String d : deadends)
            dead[Integer.parseInt(d)] = true;
        if (dead[0]) return -1;
        dead[0] = true;
        
        int t = Integer.parseInt(target), ans = 0;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
        while(list.size() > 0) {
            int n = list.size();
            for(int i = 0; i < n; i++) {
                int cur = list.pollFirst();
                if (cur == t) return ans;
                for(int m = 1; m <= 1000; m *= 10) {
                    int x = (cur % (m* 10)) / m;
                    int y = x == 9 ? cur - (m*9) : cur + m;
                    if (!dead[y]) {list.offerLast(y); dead[y] = true;}
                    y = x == 0 ? cur + (m*9) : cur - m;
                    if (!dead[y]) {list.offerLast(y); dead[y] = true;}
                }
            }
            ans++;
        }
        return -1;
    }

Log in to reply
 

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