Force buckle, 752-open turntable lock

This question is medium,But I think it's still very difficult,Learned from my brother,Just a little bit of sharing.

你有一个带有四个圆形拨轮的转盘锁.每个拨轮都有10个数字
： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ .
每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’,‘0’ 变为 ‘9’ .
And each spin can only spin one digit of the dial.

锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串.

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转.
字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 .

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”.
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的,
因为当拨动到 “0102” 时这个锁就会被锁定

输入: deadends = [“8888”], target = “0009”
输出：1
解释：把最后一位反向旋转一次即可 “0000” -> “0009”.

输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出：-1
解释：无法旋转到目标数字且不被锁定.

This question can be used typically BFS 算法,广度优先遍历算法.

To use the idea of ​​breadth-first traversal algorithm.总结一下：

1. First traverse to enumerate all password combinations,Of course, exhaustion also requires certain laws of symbols to exhaustively.
   比如：,从“0000”开始,转一次,会出现“1000”、“9000”、“0100”、“0900”、“0010”、“0090”、“0001”、“0009”这样共8种情况.Then to the next time,再以这 8 password-based,Do it again for each password,Just list all the situations.

2. To take into account when exhaustive,It is possible to go back.
   比如：从“0000”走到“1000”,But right next time“1000”when exhausted,会出现“0000”,This will cause an infinite loop.

3. 按照题目的要求,判断到达 target 就可以结束,and returns the last recorded number of toggles.

4. 也要对 deadends This dead code is handled,That is to say, in this case, this judgment should be skipped.

不多逼逼,看代码,There are more detailed instructions in the code：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Demo752 {
    
    public static void main(String[] args) {
    
        String[] str = {
    "8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        String target = "8888";
        System.out.println(openLock(str, target));
    }

    public static int openLock(String[] deadends, String target) {
    
        // Save dead codes that need to be skipped
        Set<String> strings = new HashSet<>();
        for (String deadend : deadends) {
    
            strings.add(deadend);
        }

        // Record all passwords that have been exhausted,防止回头路
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        //Start performing a breadth-first search
        int step = 0;
        queue.offer("0000");
        visited.add("0000");

        while (!queue.isEmpty()) {
    
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
    
                String str = queue.poll();

                //Determine whether the current password is qualified,Unqualified skip directly
                if (strings.contains(str)) {
    
                    continue;
                }
                // The password reaches the end,返回路径长度
                if (str.equals(target)) {
    
                    return step;
                }

                // Qualified but unfinished nodes are added to the queue by traversing adjacent nodes
                // 使用4is because the string length is 4
                for (int j = 0; j < 4; j++) {
    
                    //Get data up
                    String up = plusOne(str, j);
                    if (!visited.contains(up)) {
    
                        queue.offer(up);
                        visited.add(up);
                    }
                    //Get data down
                    String down = minusOne(str, j);
                    if (!visited.contains(down)) {
    
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        // If exhausted,没有结果,就返回-1
        return -1;
    }

    //Will be the first of the number currently givenjShift one bit up
    public static String plusOne(String s, int j) {
    
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
    
            ch[j] = '0';
        } else {
    
            ch[j] += 1;
        }
        return new String(ch);
    }

    //Will be the first of the number currently givenjShift down one digit
    public static String minusOne(String str, int j) {
    
        char[] ch = str.toCharArray();
        if (ch[j] == '0') {
    
            ch[j] = '9';
        } else {
    
            ch[j] -= 1;
        }
        return new String(ch);
    }
}

The above code is fully reflected,广度优先遍历,Start from one point and expand outward step by step.

On this subject again,We can use bidirectional here too BFS.
传统的 BFS The algorithm starts from the starting point and continues to spread around,It will stop until it reaches the end.
而双向 BFS The algorithm is to start spreading from the start and end points at the same time,当两边有交集的时候停止.

These two ideas actually follow Big O notation to analyze,It has both worst complexity O(N),But in fact it goes both ways BFS It will still be chunky,双向 BFS In fact, it only needs to traverse half of the number and the result will appear.

不过双向 BFS There is also a necessary restriction.It has to know where the end point is.

代码演示,There are also slight notes：

    public static int openLock(String[] deadends, String target) {
    
        // Save dead codes that need to be skipped
        Set<String> strings = new HashSet<>();
        for (String deadend : deadends) {
    
            strings.add(deadend);
        }

        // Record all passwords that have been exhausted,防止回头路
        Set<String> visited = new HashSet<>();
        Set<String> queue1 = new HashSet<>();
        Set<String> queue2 = new HashSet<>();

        //Start performing a breadth-first search
        int step = 0;
        queue1.add("0000");
        queue2.add(target);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
    
            // It cannot be modified during the traversal process hash 表的
            // 用 temp 存储 queue1 the result of the diffusion,作为中间数
            Set<String> temp = new HashSet<>();

            // 将 queue1 中的所有节点向周围扩散
            for (String str : queue1) {
    

                //Determine whether the current password is qualified,Unqualified skip directly
                if (strings.contains(str)) {
    
                    continue;
                }
                // The password reaches the end,返回路径长度
                if (queue2.contains(str)) {
    
                    return step;
                }
                visited.add(str);

                // Qualified but unfinished nodes are added to the queue by traversing adjacent nodes
                // 使用4is because the string length is 4
                for (int j = 0; j < 4; j++) {
    
                    //Get data up
                    String up = plusOne(str, j);
                    if (!visited.contains(up)) {
    
                        temp.add(up);
                    }
                    //Get data down
                    String down = minusOne(str, j);
                    if (!visited.contains(down)) {
    
                        temp.add(down);
                    }
                }
            }
            step++;
            
            //翻转
            queue1 = queue2;
            queue2 = temp;
        }
        // If exhausted,没有结果,就返回-1
        return -1;
    }