LeetCode LCR 109. 打开转盘锁

约 7 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 字符串 哈希表 广度优先搜索 LCR

题目描述

✅ LCR 109. 打开转盘锁

image-20260929004548507

image-20260929004548508

题意分析

四位转盘锁从 0000 开始，每次只能选择一位向前或向后拨一格，数字 0 与 9 循环相接。死亡状态不能进入，求合法到达目标的最少拨动次数，不可达时返回 -1。

每个四位字符串是一个状态，一次拨动连接两个相邻状态。所有操作代价都是一步，因此可以在这张隐式图上用 BFS 求最短路，邻居在搜索时生成即可。

解法：按层搜索锁状态

核心思路

[!blue]

先用集合记录死亡状态。起点无法使用时直接无解；起点合法且已经等于目标时，答案为零。其余情况下，将 0000 放入队列并立即标记已访问。

每个状态有八个候选邻居：四个位置分别上拨或下拨一次，其余位置保持不变。Java 修改字符数组，生成两种候选后恢复原字符；Go 分别用原字符串的前后片段与新数字拼接。边界数字要循环处理，确保每个候选仍是四位数字。

BFS 按拨动次数递增展开。某状态首次入队时已经由最少步数到达，之后再到达不会更优，而未来能走的边只由当前锁状态决定，所以只需展开一次。每个候选先排除死亡或已访问状态，再判断是否命中目标，否则入队并标记。

step 初始为零，每轮展开前先加一，并固定当前队列大小。此时队列中的旧状态距离为 step-1，从它们生成的新状态距离恰好为 step，所以命中目标即可直接返回。固定层大小能防止刚入队的下一层状态被提前处理。

若队列耗尽，说明从起点可达的全部合法状态都已搜索，仍未找到目标就返回 -1。一共只有 10^4 种四位状态，访问标记也保证搜索一定结束。

解题步骤

  1. 建立死亡状态集合，完成代码中的端点检查；合法起点已是目标时返回零。
  2. 将起点加入队列和访问集合，初始化 step = 0。
  3. 每层先增加 step，再固定本层需要处理的状态数。
  4. 对每个旧状态生成八种一次拨动结果，跳过死亡状态和已访问状态。
  5. 候选是目标时返回 step；否则加入队列并立即标记。队列最终为空则返回 -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<>();

        visited.add("0000");
        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
}

复杂度分析

设死亡列表长度为 D，全部锁状态数为 S = 10^4。

  • 时间复杂度：期望 $O(D+S)$。建立死亡集合需要扫描 D 项，每个可达状态最多展开一次，生成八个固定长度的候选并查询哈希集合。
  • 空间复杂度：$O(D+S)$。死亡集合、访问集合和队列均不超过对应状态数量级；每个字符串固定为四位。

关键点总结

[!green]

  • 完整四位字符串才是搜索状态，一条边对应一次合法拨动。
  • 环形拨轮必须正确处理 0 与 9 的相邻关系。
  • BFS 首次入队距离最短，死亡状态负责限制可达范围，访问集合负责去重。
  • step 在层前增加，表示这一轮生成的邻居所需步数，而非当前出队状态的步数。

易错点总结

[!yellow]

  • 把某一位数字单独当状态，会丢失其他拨轮的信息，无法判断死亡组合。
  • 同一次候选生成改变多位，产生不对应单次操作的边；Java 复用字符数组时每个位置结束后要恢复原值。
  • 忘记循环边界，会漏掉从零向后或从九向前的合法邻居。
  • 起点未登记访问，可能被相邻状态再次加入队列。
  • 层内动态读取队列长度或在每个节点后增加步数，会让 step 不再表示最短层数。
  • 题面保证目标不在死亡列表中，搜索中仍要过滤所有死亡中间状态，不能穿过它们到达目标。

相似题目

题目 难度 关联与区别
773. 滑动谜题 困难 同样把完整局面编码为状态，按一次合法操作生成邻居，再用BFS求最少步数。
127. 单词接龙 困难 同样搜索单位边状态图，原题邻居是合法字典词，本题邻居由转动某一位生成。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/42019357
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！