开锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

题解

int openLock(String[] deadends, String target) {
        String start = "0000";

        Set<String> deadset = new HashSet<>();
        for(String str : deadends) {
            if (str.equals(start)){
                return  -1;
            }else {
                deadset.add(str);
            }
        }

        LinkedList<String> queue = new LinkedList<>();
        Set<String> visted = new HashSet<>();
        int val = 0;

        queue.offer(start);
        visted.add(start);
        while (!queue.isEmpty()) {

            int n = queue.size();
            while (n-- != 0) {
                String curr = queue.poll();

                if (curr.equals(target)) {
                    return val;
                }
                for (int i = 0; i < 4; i++) {
                    String next = curr.substring(0, i) + (char)((curr.charAt(i) - '0' + 9) % 10 + '0') + curr.substring(i+1);

                    if (!visted.contains(next) && !deadset.contains(next)) {
                        queue.offer(next);
                        visted.add(next);
                    }
                }

                for (int i = 0; i < 4; i++) {
                    String next = curr.substring(0, i) + (char)((curr.charAt(i) - '0' + 1) % 10 + '0') + curr.substring(i+1);
                    if (!visted.contains(next) && !deadset.contains(next)) {
                        queue.offer(next);
                        visted.add(next);
                    }
                }
            }

            val++;
        }
        return  -1;

    }

1. 当队列不为空时对目前队列内的内容进行计算（while (n-- != 0)的作用：因为后面会不断往队列里新加内容，所以要对队列需取出内容的数量做限制），

2. 获得操作一次后的可能结果并判断：
   四个可拨动位置，可拨上或拨下一位数，所以共有 8 中可能。

3. 将未访问过的、不在死锁列表的加入队列，等待下一轮计算。

4. 该轮计算没有找到目标值，旋转次数+1， 重复 1。

备注：

(curr.charAt(i) - '0' + 1) % 10 + '0')结果为 int，需强制转码为 char。