LeetCode LCR 109. 打开转盘锁
目录
题目描述
题意分析
一把四位数字的转盘锁，每个轮盘上刻着
0到9且首尾相接（9再拨一格回到0）。一次操作只能把某一个轮盘拨动一格。锁的初始状态是"0000"，给定一组deadends（一旦拨到这些状态锁就卡死）和一个target，问最少拨多少次能到达target，做不到返回 -1。「每次拨一格」定义了状态之间的相邻关系，「最少次数」说明这是最短路。把每个四位字符串看成一个节点、把一次合法拨动看成一条权为 1 的边，问题就是求
"0000"到target的最短路径长度。边权全为 1，BFS 即可。状态空间是完全确定的：$10^4 = 10000$ 个节点，每个节点有 $4 \times 2 = 8$ 个邻居。规模小到可以放心地全图搜索，这也解释了为什么题目敢把
deadends的长度放到 500——即使把状态全部访问一遍也只有一万次。「首尾相接」这个设定要单独留意：
0往下拨得到9，9往上拨得到0，也就是所有加减都要对 10 取模。这是本题最容易在细节上翻车的地方。
deadends的语义是「不可进入的节点」而不是「不可经过的边」，所以它既要挡住中间状态，也要挡住起点和终点："0000"本身在deadends里时一步都走不了，target在deadends里时永远无法合法到达，两种情况都返回 -1。边界：
target恰好是"0000"时答案是 0（一次都不用拨）；deadends可能把target完全围死，此时搜索会自然耗尽队列并返回 -1。
解法：哈希表统计状态
核心思路
暴力做法是从
"0000"出发递归地尝试每一种拨动序列。状态可以反复经过，路径数无穷，必须靠层数上限来截断，本质上是在做没有记忆的搜索，指数级重复。瓶颈在于同一个锁的状态被沿不同路径反复展开。而「从某个状态出发还需要多少步到
target」只取决于这个状态本身，与它是怎么被拨出来的无关——这条无后效性正是把搜索改成 BFS 的依据。BFS 的做法是逐层扩散：第 0 层是
"0000"，第 1 层是拨一次能到的 8 个状态，第 2 层是拨两次能到的状态，以此类推。某个状态第一次被访问时所处的层号就是它的最短步数。邻居的生成是纯计算的，不需要任何预先建图：对四个位置逐一处理，把该位数字
+1或-1后对 10 取模，其余三位保持不变，共得到 8 个候选。这是一张隐式图——边不是给定的数据，而是由规则现场推导出来的。不变量是：队列中的状态按到
"0000"的步数非递减排列；每个状态最多入队一次，入队时即被标记为已访问。deadends与visited在扩展时扮演同一个角色——都表示「这个节点不许进入」，因此可以在同一处判断里一起挡掉。两个前置判断可以省掉整轮搜索：
"0000"在deadends里则起点就死，直接 -1；target等于"0000"则答案是 0。注意这两条的顺序不能反——如果target就是"0000"而"0000"又在deadends里，锁一开始就是卡死的，应当返回 -1 而不是 0。计数上用
step记录当前正在生成的是第几层。每处理完一整层前先++step，于是在展开某个状态时若生成出target，target恰好属于第step层，可以立刻返回step而不必等它出队。队列耗尽仍未命中，说明
target被deadends隔离或本身就是死亡状态，返回 -1。
解题步骤
- 把
deadends装进哈希集合。为什么：后面每生成一个候选都要判断它是否死亡，共约 $8 \times 10^4$ 次查询，用数组线性扫描会乘上 500 倍；集合把单次查询压到常数。- 先判
"0000"是否在死亡集合中，是则返回 -1。为什么排在最前：起点不可进入意味着连第 0 层都不成立，后面的一切判断都失去前提。- 再判
target是否等于"0000"，是则返回 0。为什么排在起点判断之后：见上文，两条同时成立时应当返回 -1；顺序写反会在deadends = ["0000"]、target = "0000"时错误地返回 0。- 队列初始化为
["0000"]，访问集合初始化为{"0000"}，step = 0。为什么起点要立刻标记：否则它会被自己的邻居再次推入队列，产生一圈无意义的往返。- 外层
while循环里第一件事就是++step。为什么先加：进入循环体时队列里装的是第step - 1层，本轮生成的是第step层，先加就能让「命中target时直接返回step」成立，不必再算偏移。- 用固定下来的
size = q.size()精确处理一整层。为什么要先固定：循环体内会往队尾追加下一层的状态，用动态的q.size()作条件会让两层混流，step与真实步数脱节。- 对出队状态的四个位置分别生成「上拨」和「下拨」两个候选。为什么必须对 10 取模：轮盘首尾相接，
9上拨是0、0下拨是9；忘记取模会得到:或/这样的非数字字符，整个状态空间被撕裂，很多路径凭空消失。- 对每个候选先判「已访问或已死亡」，成立则跳过。为什么两者合并成一次判断：从扩展的角度看它们是同一件事——都表示这个节点不允许进入。这一步也顺带保证了后面的
target判断只会作用在合法状态上。- 再判候选是否等于
target，是则返回step。为什么这个判断必须排在死亡判断之后：如果先比target，当target自己就在deadends里时会返回一个根本走不通的步数，而正确答案是 -1。这是本题最隐蔽的一处顺序陷阱。- 否则入队并立刻标记为已访问。为什么入队即标记：BFS 的通用去重原则，等出队再标记会让同一状态被多个邻居重复推入，队列规模成倍膨胀。
- 队列耗尽后返回 -1。为什么：所有从起点可达且不死亡的状态都已访问完毕却没碰到
target，说明不可达。以
deadends = ["8888"]、target = "0009"走一遍。前置判断：
"0000"不在死亡集合中；target不等于"0000"。队列["0000"]，visited = {"0000"}，step = 0。进入循环，
step变成 1，本层大小是 1，出队"0000"。第 0 位：下拨得
(0 - 1 + 10) % 10 = 9，候选"9000"，既不死亡也未访问，且不等于target，入队并标记；上拨得"1000"，同样入队并标记。第 1 位：得到
"0900"与"0100"，都入队。第 2 位：得到
"0090"与"0010"，都入队。第 3 位：下拨得
(0 - 1 + 10) % 10 = 9，候选"0009"，不死亡、未访问，且等于target，立刻返回step = 1。答案是 1，对应「把最后一位从 0 往下拨一格到 9」，确实一次到位。这里也能看出「先加
step再展开」的好处：命中时直接返回step，不需要任何+1的修正。再看无解用例
deadends = ["0000"]、target = "8888"：第一条前置判断就命中，返回 -1，一次 BFS 都不做。最后看那处顺序陷阱：
deadends = ["0001"]、target = "0001"。若把target比较写在死亡判断之前，展开"0000"时会生成"0001"并直接返回 1；而这把锁一旦拨到"0001"就卡死了，正确答案是 -1。按正确顺序，"0001"会被死亡判断挡掉，搜索会把其余 9999 个状态全部访问完，最终返回 -1。
代码实现
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> s = new HashSet<>(Arrays.asList(deadends));
// 起点或终点本身就是死亡状态，直接无解。
if (s.contains(target) || s.contains("0000")) {
return -1;
}
if (Objects.equals(target, "0000")) {
return 0;
}
Set<String> visited = new HashSet<>();
Deque<String> q = new ArrayDeque<>();
q.offerLast("0000");
int step = 0;
while (!q.isEmpty()) {
// 先加，使命中时可以直接返回 step。
++step;
for (int i = 0, n = q.size(); i < n; ++i) {
String status = q.pollFirst();
for (String t : get(status)) {
// 已访问与已死亡在扩展时是同一件事：不允许进入。
if (visited.contains(t) || s.contains(t)) {
continue;
}
if (Objects.equals(t, target)) {
return step;
}
q.offerLast(t);
// 入队即标记，防止同一状态被重复展开。
visited.add(t);
}
}
}
return -1;
}
private char prev(char c) {
// 轮盘首尾相接：0 往下拨得到 9。
return c == '0' ? '9' : (char) (c - 1);
}
private char next(char c) {
// 轮盘首尾相接：9 往上拨得到 0。
return c == '9' ? '0' : (char) (c + 1);
}
private List<String> get(String t) {
List<String> res = new ArrayList<>();
char[] chars = t.toCharArray();
for (int i = 0; i < 4; ++i) {
char c = chars[i];
chars[i] = prev(c);
res.add(String.valueOf(chars));
chars[i] = next(c);
res.add(String.valueOf(chars));
// 还原本位，避免污染后续位置的枚举。
chars[i] = c;
}
return res;
}
}
func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
// 起点或终点本身就是死亡状态，直接无解。
if dead["0000"] || dead[target] {
return -1
}
if target == "0000" {
return 0
}
q := []string{"0000"}
visited := map[string]bool{"0000": true}
step := 0
for len(q) > 0 {
// 先加，使命中时可以直接返回 step。
step++
size := len(q)
for i := 0; i < size; i++ {
cur := q[0]
q = q[1:]
for j := 0; j < 4; j++ {
for k := -1; k <= 1; k += 2 {
// 轮盘首尾相接，加减都要对 10 取模。
next := cur[:j] + string((cur[j]-'0'+byte(k)+10)%10+'0') + cur[j+1:]
// 已访问与已死亡在扩展时是同一件事：不允许进入。
if dead[next] || visited[next] {
continue
}
if next == target {
return step
}
q = append(q, next)
// 入队即标记，防止同一状态被重复展开。
visited[next] = true
}
}
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(b^d \cdot d)$，本题即 $O(10^4 \times 8 \times 4)$ 的常数级上界，其中 $b = 10$ 是每位的取值数、$d = 4$ 是位数。凭什么：状态总数固定为 $10^4$，每个状态最多入队一次，出队时生成 8 个候选，每个候选要拼接一个长度为 4 的字符串并做哈希。整体不超过十万次基本操作。
空间复杂度：$O(b^d)$，即 $O(10^4)$。凭什么：访问集合最坏要装下全部状态，队列在某一层最宽时也可能容纳数千个状态，死亡集合是 $O( deadends )$，三者都不超过状态总数。
关键点总结
- 状态是字符串、邻居由规则现场推导的题目属于「隐式图 BFS」：不要预先建图，直接在扩展时生成邻居，建图的代价往往比搜索本身还大。
- 循环轮盘的相邻关系必须靠对 10 取模来表达，
0与9互为邻居；凡是出现「首尾相接」「环形」字样，先想清楚取模写法再动手。deadends与visited在扩展时语义相同（都表示不可进入），合并成一次判断能少写一层分支；但它们的来源不同，前者是输入约束、后者是算法状态，讲解时要分清。- 判断顺序是本题的核心陷阱：必须先挡死亡状态、再比
target，否则target自己在deadends里时会返回一个走不通的步数。同理，起点死亡的判断要排在target == "0000"之前。- 把
++step放在层循环之前，命中时直接返回step，可以彻底避免在+1上反复调试——这是分层 BFS 的一个实用写法。- 面试视角：状态空间只有一万，最优化的答案是双向 BFS——从
"0000"和target两端同时扩散，每轮扩展较小的一侧，能把搜索量从 $b^d$ 降到约 $2b^{d/2}$。被问到优化时给出这条即可。
易错点总结
- 忘记
target在deadends里的情形：deadends = ["0001"]、target = "0001"会返回 1，而正确答案是 -1。- 把
target相等判断写在死亡判断之前：同上例，判断顺序一颠倒就会放行一个不可进入的状态。- 把
target == "0000"判断写在起点死亡判断之前：deadends = ["0000"]、target = "0000"会返回 0，而锁一开始就卡死，正确答案是 -1。- 拨动时忘记取模：
"0000"的第 0 位下拨若直接写成c - 1，会得到字符/而不是'9'，deadends = []、target = "9000"的答案会从 1 变成 3（只能靠九次上拨绕回去，且中间状态还可能出错）。prev和next的边界写反：把c == '9' ? '0'误写成c == '0' ? '9'用在上拨里，target = "0001"会算不出 1 步解。- 生成候选时不还原
chars[i]："0000"的第 0 位停在1后，第 1 位的枚举会基于"1000"展开，生成出与原状态相差两位的非法邻居，路径长度全面失真。"0000"没有预先放进visited：它会被自己的邻居再次推入队列，deadends = []、target = "0002"时队列里出现重复状态，步数虽仍正确但访问量成倍增加。- 出队时才标记已访问：
deadends = []、target = "9999"时同一状态被 8 个邻居重复入队，队列规模膨胀数倍，接近超时。- 用
q.size()作为内层动态条件：本层与下一层混流，step不再等于层号，target = "0202"这类需要多层的用例返回的步数偏小。- 用
==比较 Java 字符串：候选串是new String(...)构造出来的，t == target恒为假，所有用例都会走到队列耗尽并返回 -1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 752. 打开转盘锁 | 中等 | 与本题同题，可直接套用同一份代码 |
| 127. 单词接龙 | 困难 | 邻居是把某位换成任意字母且必须落在词典中，返回的是单词个数而非步数 |
| 433. 最小基因变化 | 中等 | 字符集是 ACGT，合法状态由基因库限定，无「死亡状态」概念 |
| 773. 滑动谜题 | 困难 | 邻居由空格可交换的位置决定，需把二维棋盘序列化成字符串当状态 |
| 1345. 跳跃游戏 IV | 困难 | 邻居包含所有同值下标，必须用完即清空该值的列表以免退化成平方复杂度 |
| 909. 蛇梯棋 | 中等 | 一步的邻居是骰子的六个结果，还要处理编号到坐标的蛇形映射 |
| 542. 01 矩阵 | 中等 | 显式网格上的多源 BFS，可对照体会隐式图与显式图在建边上的差别 |
| LCR 108. 单词接龙 | 困难 | 与 127 同题，同属「字符串状态 BFS」，但去重靠从词典中删除而非集合 |