752. 打开转盘锁

# 题目

## 752. 打开转盘锁

[https://leetcode-cn.com/problems/open-the-lock/](https://leetcode-cn.com/problems/open-the-lock/)

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
```

**提示：**

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

# 题解

## 思路

广度优先搜索。死亡数字其实就相当于已经访问的节点，初始化时加入到访问节点中，接下来就是bfs的常规套路

## 代码

```javascript
/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
    const start = new Array(4).fill(0);
    // 已经访问过的
    const visit = new Set();
    const queue = [start];
    deadends.forEach(element => {
        visit.add(element);
    });

// 获取下一个值
function getNextArr(arr, index, num) {
    const nextArr = [...arr];
    if (nextArr[index] === 0 && num === -1) {
        nextArr[index] = 9;
    } else if (nextArr[index] === 9 && num === 1) {
        nextArr[index] = 0;
    } else {
        nextArr[index] += num;
    }

return nextArr;
}

```

## 参考

### 双向 BFS

我们知道，递归树的展开形式是一棵多阶树。

使用朴素 BFS 进行求解时，队列中最多会存在“两层”的搜索节点。

因此搜索空间的上界取决于 **目标节点所在的搜索层次的深度所对应的宽度**。

下图展示了朴素 BFS 可能面临的搜索空间爆炸问题：

![image.png](/media/202106/2021-06-29_235839.png)

**在朴素的 BFS 实现中，空间的瓶颈主要取决于搜索空间中的最大宽度。**

那么有没有办法让我们不使用这么宽的搜索空间，同时又能保证搜索到目标结果呢？

「双向 BFS」 可以很好的解决这个问题：

**同时从两个方向开始搜索，一旦搜索到相同的值，意味着找到了一条联通起点和终点的最短路径。**

对于「有解」、「有一定数据范围」同时「层级节点数量以倍数或者指数级别增长」的情况，「双向 BFS」的搜索空间通常只有「朴素 BFS」的空间消耗的几百分之一，甚至几千分之一。

![image.png](/media/202106/2021-06-29_235839.png)

「双向 BFS」的基本实现思路如下：

1. 创建「两个队列」分别用于两个方向的搜索；
2. 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
3. 为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
4. 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。

「双向 BFS」基本思路对应的伪代码大致如下：

- Java

```
d1、d2 为两个方向的队列
m1、m2 为两个方向的哈希表，记录每个节点距离起点的
    
// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(!d1.isEmpty() && !d2.isEmpty()) {
    if (d1.size() < d2.size()) {
        update(d1, m1, m2);
    } else {
        update(d2, m2, m1);
    }
}

// update 为从队列 d 中取出一个元素进行「一次完整扩展」的逻辑
void update(Deque d, Map cur, Map other) {}
```

回到本题，我们看看如何使用「双向 BFS」进行求解。

估计不少同学是第一次接触「双向 BFS」，因此这次我写了大量注释。

建议大家带着对「双向 BFS」的基本理解去阅读。

![image.png](/media/202106/2021-06-29_235839.png)

**代码**

- Java

```
class Solution {
    String t, s;
    Set<String> set = new HashSet<>();
    public int openLock(String[] _ds, String _t) {
        s = "0000";
        t = _t;
        if (s.equals(t)) return 0;
        for (String d : _ds) set.add(d);
        if (set.contains(s)) return -1;
        int ans = bfs();
        return ans;
    }
    int bfs() {
        // d1 代表从起点 s 开始搜索（正向）
        // d2 代表从结尾 t 开始搜索（反向）
        Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        /*
         * m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来
         * e.g.
         * m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋转 1 次而来
         * m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋转 3 次而来
         */
        Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
        d1.addLast(s);
        m1.put(s, 0);
        d2.addLast(t);
        m2.put(t, 0);

/*
         * 只有两个队列都不空，才有必要继续往下搜索
         * 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
         * e.g. 
         * 例如，如果 d1 为空了，说明从 s 搜索到底都搜索不到 t，反向搜索也没必要进行了
         */
        while (!d1.isEmpty() && !d2.isEmpty()) {
            int t = -1;
            if (d1.size() <= d2.size()) {
                t = update(d1, m1, m2);
            } else {
                t = update(d2, m2, m1);
            }
            if (t != -1) return t;
        }
        return -1;       
    }
    int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
        String poll = deque.pollFirst();
        char[] pcs = poll.toCharArray();
        int step = cur.get(poll);
        // 枚举替换哪个字符
        for (int i = 0; i < 4; i++) {
            // 能「正向转」也能「反向转」，这里直接枚举偏移量 [-1,1] 然后跳过 0
            for (int j = -1; j <= 1; j++) {
                if (j == 0) continue;

// 求得替换字符串 str
                int origin = pcs[i] - '0';
                int next = (origin + j) % 10;
                if (next == -1) next = 9;

char[] clone = pcs.clone();
                clone[i] = (char)(next + '0');
                String str = String.valueOf(clone);

if (set.contains(str)) continue;
                if (cur.containsKey(str)) continue;

// 如果在「另一方向」找到过，说明找到了最短路，否则加入队列
                if (other.containsKey(str)) { 
                    return step + 1 + other.get(str);
                } else {
                    deque.addLast(str);
                    cur.put(str, step + 1);
                }
            }
        }
        return -1;
    }
}
```

---

### AStar 算法

可以直接根据本题规则来设计 A* 的「启发式函数」。

比如对于两个状态 `a` 和 `b` 可直接计算出「理论最小转换次数」：**不同字符的转换成本之和** 。

**需要注意的是：由于我们衡量某个字符 `str` 的估值是以目标字符串 `target` 为基准，因此我们只能确保 `target` 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。**

这一点十分关键，在代码层面上体现在 `map.get(str).step > poll.step + 1` 的判断上。

注意：本题用 A* 过了，但通常我们需要先「确保有解」，A* 的启发搜索才会发挥真正价值。而本题，除非 `t` 本身在 `deadends` 中，其余情况我们无法很好提前判断「是否有解」。对于无解的情况 A* 效果不如「双向 BFS」。

![image.png](/media/202106/2021-06-29_235839.png)

代码：

- Java

```
class Solution {
    class Node {
        String str;
        int val, step;
       /**
        *  str : 对应字符串
        *  val : 估值（与目标字符串 target 的最小转换成本）
        *  step: 对应字符串是经过多少步转换而来
        */
        Node(String _str, int _val, int _step) {
            str = _str;
            val = _val;
            step = _step;
        }
    }
    int f(String str) {
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            int cur = str.charAt(i) - '0', target = t.charAt(i) - '0';
            int a = Math.min(cur, target), b = Math.max(cur, target);
            // 在「正向转」和「反向转」之间取 min
            int min = Math.min(b - a, a + 10 - b);
            ans += min;
        }
        return ans;
    }
    String s, t;
    Set<String> set = new HashSet<>();
    public int openLock(String[] ds, String _t) {
        s = "0000";
        t = _t;
        if (s.equals(t)) return 0;
        for (String d : ds) set.add(d);
        if (set.contains(s)) return -1;
        
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Node> map = new HashMap<>();
        Node root = new Node(s, f(s), 0);
        q.add(root);
        map.put(s, root);
        while (!q.isEmpty()) {
            Node poll = q.poll();
            char[] pcs = poll.str.toCharArray();
            int step = poll.step;
            if (poll.str.equals(t)) return step;
            for (int i = 0; i < 4; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (j == 0) continue;
                    int cur = pcs[i] - '0';
                    int next = (cur + j) % 10;
                    if (next == -1) next = 9;

char[] clone = pcs.clone();
                    clone[i] = (char)(next + '0');
                    String str = String.valueOf(clone);

if (set.contains(str)) continue;
                    // 如果 str 还没搜索过，或者 str 的「最短距离」被更新，则入队
                    if (!map.containsKey(str) || map.get(str).step > step + 1) {
                        Node node = new Node(str, step + 1 + f(str), step + 1);
                        map.put(str, node);
                        q.add(node);
                    }
                }
            }
        }
        return -1;
    }
}
```

---

### IDA* 算法

同样我们可以使用基于 `DFS` 的启发式 IDA* 算法：

- 仍然使用 `f()` 作为估值函数
- 利用旋转次数有限：总旋转次数不会超过某个阈值 \maxmax。
- 利用「迭代加深」的思路找到最短距离

理想情况下，由于存在正向旋转和反向旋转，每一位转轮从任意数字开始到达任意数字，消耗次数不会超过 55 次，因此理想情况下可以设定 \max = 5 * 4max=5∗4 。

但考虑 `deadends` 的存在，我们需要将 \maxmax 定义得更加保守一些：\max = 10 * 4max=10∗4 。

**但这样的阈值设定，加上 IDA\* 算法每次会重复遍历「距离小于与目标节点距离」的所有节点，会有很大的 TLE 风险。**

**因此我们需要使用动态阈值：不再使用固定的阈值，而是利用 `target` 计算出「最大的转移成本」作为我们的「最深数量级」。**

PS. 上述的阈值分析是科学做法。对于本题可以利用数据弱，直接使用 \max = 5 * 4max=5∗4 也可以通过，并且效果不错。

但必须清楚 \max = 5 * 4max=5∗4 可能是一个错误的阈值，本题起点为 `0000`，考虑将所有正向转换的状态都放入 `deadends` 中，`target` 为 `2222`。这时候我们可以只限定 `0000` 先变为 `9999` 再往回变为 `2222` 的通路不在 `deadends` 中。

这时候使用 \max = 5 * 4max=5∗4 就不对，但本题数据弱，可以通过（想提交错误数据拿积分吗？别试了，我已经提交了 ?

![image.png](/media/202106/2021-06-29_235839.png)

代码：

- Java

```
class Solution {
    String s, t;
    String cur;
    Set<String> set = new HashSet<>();
    Map<String, Integer> map = new HashMap<>();
    public int openLock(String[] ds, String _t) {
        s = "0000";
        t = _t;
        if (s.equals(t)) return 0;
        for (String d : ds) set.add(d);
        if (set.contains(s)) return -1;

int depth = 0, max = getMax();
        cur = s;
        map.put(cur, 0);
        while (depth <= max && !dfs(0, depth)) {
            map.clear();
            cur = s;
            map.put(cur, 0);
            depth++;
        }
        return depth > max ? -1 : depth;
    }
    int getMax() {
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            int origin = s.charAt(i) - '0', next = t.charAt(i) - '0';
            int a = Math.min(origin, next), b = Math.max(origin, next);
            int max = Math.max(b - a, a + 10 - b);
            ans += max;
        }
        return ans;
    }
    int f() {
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            int origin = cur.charAt(i) - '0', next = t.charAt(i) - '0';
            int a = Math.min(origin, next), b = Math.max(origin, next);
            int min = Math.min(b - a, a + 10 - b);
            ans += min;
        }
        return ans;
    }
    boolean dfs(int u, int max) {
        if (u + f() > max) return false;
        if (f() == 0) return true;
        String backup = cur;
        char[] cs = cur.toCharArray();
        for (int i = 0; i < 4; i++) {
            for (int j = -1; j <= 1; j++) {
                if (j == 0) continue;
                int origin = cs[i] - '0';
                int next = (origin + j) % 10;
                if (next == -1) next = 9;
                char[] clone = cs.clone();
                clone[i] = (char)(next + '0');
                String str = String.valueOf(clone);  
                if (set.contains(str)) continue;
                if (!map.containsKey(str) || map.get(str) > u + 1) {
                    cur = str;
                    map.put(str, u + 1);
                    if (dfs(u + 1, max)) return true;
                    cur = backup;
                }
            }
        }
        return false;
    }
}
```