LeetCode 752. 打开转盘锁

◎

本节目标

将转盘字符串视为隐式图节点，用单向 BFS 求最少转动次数。

这道题把网格与状态图搜索从坐标推广到字符串：每个四位组合是一个状态，转动任意一位的一格就是一条边。

查看 LeetCode 原题

朴素思路与瓶颈

深度优先枚举所有组合可以判断可达，却不能保证第一次遇到目标时步数最少。每次转动的代价都相同，应该从 0000 开始按层扩展；第一层是一步可达状态，第二层是两步可达状态。

隐式状态图与入队标记

不必预先建立一万种组合的边表。取出当前字符串后，依次把四个位置的数字加一、减一并处理 9 → 0、0 → 9 的环绕，就生成八个邻居。

死亡状态不能进入队列。更关键的是，生成一个合法新状态后立刻加入 visited 再入队：同一层的另一个父状态即使也能到达它，也会被拒绝。这样每个状态只进入一次队列，层数才稳定地对应最短步数。

代码实现

两种实现使用 dead 集合过滤死亡组合，用队列分层维护距离。起点死亡直接返回 -1；目标就是 0000 时，起点所在的第零层返回 0。

C++

C++17

#include <queue>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        const string start = "0000";
        if (dead.count(start) > 0) {
            return -1;
        }

        queue<string> states;
        unordered_set<string> visited;
        states.push(start);
        visited.insert(start);
        int distance = 0;

        while (!states.empty()) {
            int layerSize = static_cast<int>(states.size());
            for (int count = 0; count < layerSize; count++) {
                string current = states.front();
                states.pop();
                if (current == target) {
                    return distance;
                }

                for (int pos = 0; pos < 4; pos++) {
                    for (int change : {-1, 1}) {
                        string next = current;
                        next[pos] = static_cast<char>(
                            (next[pos] - '0' + change + 10) % 10 + '0');
                        if (dead.count(next) == 0 && visited.insert(next).second) {
                            // 新状态入队时立刻访问，保证不会重复入队。
                            states.push(next);
                        }
                    }
                }
            }
            distance++;
        }

        return -1;
    }
};

Python

Python 3

from collections import deque


class Solution:
    def openLock(self, deadends: list[str], target: str) -> int:
        dead = set(deadends)
        start = "0000"
        if start in dead:
            return -1

        states = deque([start])
        visited = {start}
        distance = 0

        while states:
            for _ in range(len(states)):
                current = states.popleft()
                if current == target:
                    return distance

                for pos in range(4):
                    digit = int(current[pos])
                    for change in (-1, 1):
                        next_state = (
                            current[:pos]
                            + str((digit + change) % 10)
                            + current[pos + 1 :]
                        )
                        if next_state not in dead and next_state not in visited:
                            # 新状态入队时立刻访问，保证不会重复入队。
                            visited.add(next_state)
                            states.append(next_state)
            distance += 1

        return -1

复杂度分析

设实际进入搜索的状态数为 N，每个状态固定生成八个长度为 4 的字符串邻居。时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 最多为 10^4。

易错点

• 起点在死亡集合中仍然开始搜索。
• 目标是起点时返回 1，混淆了起点距离和一次操作。
• 只生成加一或减一方向，漏掉可行最短路。
• 出队后才标记访问，同一组合会被多个父状态重复入队。

模式迁移

密码、单词、棋盘布局等只要能从当前状态即时构造下一状态，都可视为隐式图。若每条操作代价相同，先写“邻居生成器”，再套入队即访问的 BFS 骨架。