【力扣752】打开转盘锁

题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
解释：无法旋转到目标数字且不被锁定。

提示：

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target 不在 deadends 之中
• target 和 deadends[i] 仅由若干位数字组成

实现代码

方式一

广度优先算法（BFS），每次密码状态都能转动衍生出8种状态，那么也就是每个树节点都有8个子节点

public int openLock(String[] deadends, String target) {

    Set<String> deadsSet = new HashSet<>(Arrays.asList(deadends));
    if (deadsSet.contains("0000")) return -1;

    Queue<String> queue = new LinkedList<>();
    queue.offer("0000");
    int n = 0;
    // 防止死循环
    Set<String> visited = new HashSet<>();
    visited.add("0000");
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 每一层
        for (int i = 0; i < size; i++) {
            String poll = queue.poll();
            if (poll.equals(target)) {
                return n;
            }
            // 开始旋转，4个转盘
            for (int j = 0; j < 4; j++) {
                // 正旋转
                String positiveStr = rotate(poll, j, 1);
                if (!visited.contains(positiveStr) && !deadsSet.contains(positiveStr)) {
                    queue.offer(positiveStr);
                    visited.add(positiveStr);
                }
                // 负旋转
                String negativeStr = rotate(poll, j, -1);
                if (!visited.contains(negativeStr) && !deadsSet.contains(negativeStr)) {
                    queue.offer(negativeStr);
                    visited.add(negativeStr);
                }
            }
        }
        n++;
    }
    return -1;
}

private String rotate(String s, int index, int step) {

    char[] chars = s.toCharArray();
    char c = chars[index];
    if (step == 1) {
        chars[index] = c == '9' ? '0' : (char) (c + 1);
    } else {
        chars[index] = c == '0' ? '9' : (char) (c - 1);
    }
    return new String(chars);
}

时间复杂度

4个转盘锁，每个有10种数字，那么一共就有10^4种组合状态，并且每种状态都有8种旋转选择，那么一共8*10^4，假设转盘锁的个数为n，m为数字，时间复杂度就是O(m^n)

空间复杂度

主要的额外空间消耗来自：

1. visited ：在最坏情况下需要存储所有可能的状态，空间复杂度为O(10^4)
2. BFS队列：在最坏情况下可能包含一层的所有状态，空间复杂度也是O(10^4)
3. deadsSet ：限制了1 <= deadends.length <= 500

因此总的空间复杂度为O(2*10^4)，即为O(m^n)。

方式二

双向BFS，普通BFS随着树的深度越深其时间复杂度和时间复杂度越高，而双向BFS是从起点和终点同时进行搜索，其效率大大提升

class Solution {
    public int openLock(String[] deadends, String target) {

        Set<String> deadendSet = new HashSet<>();
        for (String deadend : deadends) {
            deadendSet.add(deadend);
        }
        // 初始密码的0000
        if ("0000".equals(target)) {
            return 0;
        }
        if (deadendSet.contains("0000") || deadendSet.contains(target)) {
            return -1;
        }
        // 正向扩散集合，从起点0000开始出发
        Set<String> q1 = new HashSet<>();
        q1.add("0000");
        // 反向扩散集合，从终点target开始出发
        Set<String> q2 = new HashSet<>();
        q2.add(target);
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        int n = 0;
        while (!q1.isEmpty() && !q2.isEmpty()) {
            Set<String> newQ = new HashSet<>();
            n++;
            for (String s : q1) {
                // 每个状态进行扩散
                for (String adjacent : getAdjacentList(s)) {

                    if (q2.contains(adjacent)) {
                        return n;
                    }
                    if (!visited.contains(adjacent) && !deadendSet.contains(adjacent)) {
                        newQ.add(adjacent);
                        visited.add(adjacent);
                    }
                }
            }
            q1 = newQ;
            // 把元素少的作为下一次扩散的集合q1，目的是两个方向的集合交替扩散
            if (q1.size() > q2.size()) {
                Set<String> tmp = q1;
                q1 = q2;
                q2 = tmp;
            }
        }
        return -1;
    }

    private List<String> getAdjacentList(String s) {

        List<String> list = new ArrayList<>();
        for (int j = 0; j < 4; j++) {
            // 正旋转
            String positiveStr = rotate(s, j, 1);
            list.add(positiveStr);
            // 负旋转
            String negativeStr = rotate(s, j, -1);
            list.add(negativeStr);
        }
        return list;
    }

    private String rotate(String s, int index, int step) {

        char[] chars = s.toCharArray();
        char c = chars[index];
        if (step == 1) {
            chars[index] = c == '9' ? '0' : (char) (c + 1);
        } else {
            chars[index] = c == '0' ? '9' : (char) (c - 1);
        }
        return new String(chars);
    }
}

代码讲解

// 把元素少的作为下一次扩散的集合q1，目的是两个方向的集合交替扩散
if (q1.size() > q2.size()) {
    Set<String> tmp = q1;
    q1 = q2;
    q2 = tmp;
}

q1负责下一次的扩散，所以每次都是将下一次扩散的集合交给q1，为什么每次都是将元素少的进行下一次扩散呢?

可以想象一下，外卖员A送外卖给B，其中A到B的路线有很多，并且越往后走岔路越多，普通BFS是A单向跑向B送过去，而双向BFS是A和B相向而行，为了尽早相遇，也就是A和B都不要走太远（因为越往前走岔路越多，走的弯路也就越多），A跑一点，B跑一点，直到两人相遇；如果只是A一直跑，那么和普通BFS没什么区别，A需要尝试很多弯路才能找到B；

（或者也可以想象迷宫的入口和出口）

注意

双向BFS一定需要有目的节点才能使用；

时间复杂度

普通BFS的时间复杂最多为10^4，双向BFS应该是8x2x10^2，也就是O(8*2*m^(n/2))

最终的时间复杂度为O(m^(n/2))

空间复杂度

主要的额外空间消耗来自：

1. visited ：在最坏情况下需要存储所有可能的状态，空间复杂度为O(10^4)
2. deadendSet ：限制了1 <= deadends.length <= 500
3. q1、q2、newQ：只存储一层的节点；

因此总的空间复杂度为O(m^n)。