752. 打开转盘锁

题目描述

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有 10 个数字：0, 1, 2, 3, 4, 5, 6, 7, 8, 9。

每个拨轮可以自由旋转：

例如把 9 变成 0
把 0 变成 9

每次旋转都只能旋转一个拨轮的一位。

锁的初始数字为：

text

"0000"

给你一个字符串列表 deadends，以及一个目标字符串 target。

如果某个数字出现在 deadends 里，那么这个状态会永久锁定，不能再被继续旋转。

请你返回：

从 "0000" 旋转到 target 所需的最小旋转次数
如果无论如何都无法到达，返回 -1

示例 1

text

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6

示例 2

text

输入：deadends = ["8888"], target = "0009"
输出：1

示例 3

text

输入：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] 仅由数字组成

核心思路

这题本质上不是字符串模拟题，而是：

每个 4 位字符串都是一个状态
一次旋转可以从一个状态走到相邻状态
每次操作代价都一样，都是 1
问从起点到目标的 最少步数

只要看到：

最少操作次数
无权图最短路

第一反应就应该是：

BFS

因为 BFS 天然适合求“最少几步到达目标”。

这题至少有两种常见做法：

解法一：普通 BFS（推荐）
解法二：双向 BFS

先理解：这题为什么是图？

比如状态：

text

"0000"

它一次可以转出 8 个相邻状态：

第一位往上 / 往下
第二位往上 / 往下
第三位往上 / 往下
第四位往上 / 往下

例如：

text

"0000" -> "1000"
"0000" -> "9000"
"0000" -> "0100"
"0000" -> "0900"
...

所以：

每个字符串是一个点
一次旋转就是一条边

这就是一个无权图最短路问题。

解法一：普通 BFS

这是这题最标准、最推荐掌握的做法。

思路拆解

BFS 从起点 "0000" 开始，一层一层往外扩展：

第 0 层："0000"
第 1 层：所有转一次能到的状态
第 2 层：所有转两次能到的状态
...

这样第一次到达 target 时，当前层数就是最少操作次数。

但要注意两类不能走的状态：

已经访问过的状态
deadends 中的死亡状态

如何生成相邻状态？

对一个 4 位字符串，我们枚举每一位：

当前位加一（9 -> 0）
当前位减一（0 -> 9）

比如当前是：

text

"0190"

如果改第三位：

往上转："0100"
往下转："0180"

我们可以写一个辅助函数，生成当前状态的所有邻居。

一步一步写出算法

第一步：先处理边界情况

如果起点本身就是死亡状态：

if (deadSet.has('0000')) {
    return -1
}

如果目标就是起点：

if (target === '0000') {
    return 0
}

第二步：把 `deadends` 放进集合

const deadSet = new Set(deadends)

这样判断一个状态是否死亡是 O(1)。

第三步：定义生成邻居函数

const getNextStates = (state: string): string[] => {
    const result: string[] = []

    for (let i = 0; i < 4; i++) {
        const chars = state.split('')
        const digit = Number(chars[i])

        chars[i] = String((digit + 1) % 10)
        result.push(chars.join(''))

        chars[i] = String((digit + 9) % 10)
        result.push(chars.join(''))
    }

    return result
}

第四步：开始 BFS

const queue: [string, number][] = ['0000', 0](<'0000', 0.md>)
const visited = new Set<string>(['0000'])

队列里存：

当前状态
到达它用了几步

第五步：不断扩展队头

while (queue.length > 0) {
    const [state, step] = queue.shift()!
    ...
}

第六步：扩展 8 个相邻状态

对于每个相邻状态：

如果是死亡状态，跳过
如果访问过了，跳过
如果等于目标，直接返回 step + 1
否则入队

代码实现（TypeScript）

function openLock(deadends: string[], target: string): number {
    const deadSet = new Set(deadends)
    if (deadSet.has('0000')) {
        return -1
    }
    if (target === '0000') {
        return 0
    }

    const getNextStates = (state: string): string[] => {
        const result: string[] = []

        for (let i = 0; i < 4; i++) {
            const chars = state.split('')
            const digit = Number(chars[i])

            chars[i] = String((digit + 1) % 10)
            result.push(chars.join(''))

            chars[i] = String((digit + 9) % 10)
            result.push(chars.join(''))
        }

        return result
    }

    const queue: [string, number][] = ['0000', 0](<'0000', 0.md>)
    const visited = new Set<string>(['0000'])

    while (queue.length > 0) {
        const [state, step] = queue.shift()!

        for (const nextState of getNextStates(state)) {
            if (deadSet.has(nextState) || visited.has(nextState)) {
                continue
            }

            if (nextState === target) {
                return step + 1
            }

            visited.add(nextState)
            queue.push([nextState, step + 1])
        }
    }

    return -1
}

复杂度分析

状态总数最多只有：

text

10^4 = 10000

因为一共就 4 位，每位 10 种可能。

所以：

时间复杂度：O(10000)，也可以写成 O(1) 状态空间意义下的常数级上界
空间复杂度：O(10000)

通常写题时写成：

时间复杂度：O(10^4)
空间复杂度：O(10^4)

更直观。

这一解法的优缺点

优点：

最标准
最容易理解
非常适合这题的数据范围

缺点：

队列会扩展不少状态
不是搜索优化版本

解法二：双向 BFS

这个做法更偏进阶，适合你想进一步理解如何减少搜索范围。

思路拆解

普通 BFS 是：

从起点一个方向往终点搜

而双向 BFS 是：

一边从起点搜
一边从终点搜
当两边搜索相遇时，就说明找到最短路了

为什么这样可能更快？

因为搜索树是指数扩张的。

如果原来要从一边搜 d 层：

改成两边各搜 d/2 层

状态数通常会少很多。

这题状态图比较规则，所以双向 BFS 是很自然的优化方法。

一步一步写出算法

第一步：准备两个前沿集合

let beginSet = new Set<string>(['0000'])
let endSet = new Set<string>([target])

还要准备：

deadSet
visited
当前步数 step

第二步：每轮优先扩展更小的一边

这样可以让搜索更均衡：

if (beginSet.size > endSet.size) {
    [beginSet, endSet] = [endSet, beginSet]
}

第三步：扩展当前这一层

对 beginSet 中每个状态生成邻居：

如果邻居在 endSet 中，说明两边相遇，直接返回答案
如果不是死亡状态且没访问过，就加入下一层集合

第四步：更新步数并进入下一轮

beginSet = nextLevel
step++

直到某一边为空，就说明无法到达。

代码实现（TypeScript）

function openLock(deadends: string[], target: string): number {
    const deadSet = new Set(deadends)
    if (deadSet.has('0000')) {
        return -1
    }
    if (target === '0000') {
        return 0
    }

    const getNextStates = (state: string): string[] => {
        const result: string[] = []

        for (let i = 0; i < 4; i++) {
            const chars = state.split('')
            const digit = Number(chars[i])

            chars[i] = String((digit + 1) % 10)
            result.push(chars.join(''))

            chars[i] = String((digit + 9) % 10)
            result.push(chars.join(''))
        }

        return result
    }

    let beginSet = new Set<string>(['0000'])
    let endSet = new Set<string>([target])
    const visited = new Set<string>(['0000', target])
    let step = 0

    while (beginSet.size > 0 && endSet.size > 0) {
        if (beginSet.size > endSet.size) {
            ;[beginSet, endSet] = [endSet, beginSet]
        }

        const nextLevel = new Set<string>()

        for (const state of beginSet) {
            if (deadSet.has(state)) {
                continue
            }

            if (endSet.has(state)) {
                return step
            }

            for (const nextState of getNextStates(state)) {
                if (deadSet.has(nextState)) {
                    continue
                }

                if (endSet.has(nextState)) {
                    return step + 1
                }

                if (visited.has(nextState)) {
                    continue
                }

                visited.add(nextState)
                nextLevel.add(nextState)
            }
        }

        beginSet = nextLevel
        step++
    }

    return -1
}

复杂度分析

最坏情况下仍然可能访问很多状态
时间复杂度上界仍然可以看成 O(10^4)
空间复杂度：O(10^4)

但在很多情况下，双向 BFS 的实际搜索量会比普通 BFS 更小。

这一解法的优缺点

优点：

搜索范围通常更小
是很经典的 BFS 优化技巧

缺点：

写法更复杂
边界处理更容易出错

两种解法对比

解法	时间复杂度	空间复杂度	特点
普通 BFS	`O(10^4)`	`O(10^4)`	最标准，最推荐
双向 BFS	`O(10^4)` 上界	`O(10^4)`	实战通常更快，但更复杂

如果你是第一次做这题，建议一定先彻底掌握普通 BFS。

手动模拟一遍普通 BFS

以：

text

deadends = ["8888"]
target = "0009"

为例。

第一步：起点

初始状态：

text

"0000"

步数是 0。

第二步：扩展 `0000`

它的一个相邻状态是：

text

"0009"

因为最后一位向下转一格：

text

0 -> 9

第三步：到达目标

此时只用了 1 步。

所以答案就是：

text

面试时最容易错的点

1. 这是最短路题，不是 DFS 题

因为每次操作代价相同，要求最少步数。

所以第一反应应该是：

不是 DFS。

2. `0` 和 `9` 是连着的

拨轮是环形的：

9 往上转变 0
0 往下转变 9

所以常见写法是：

(digit + 1) % 10
(digit + 9) % 10

3. 起点也可能是死亡状态

如果 "0000" 在 deadends 中，直接返回 -1。

4. 一定要做访问标记

否则状态会反复来回跳，比如：

text

0000 -> 0001 -> 0000 -> 0001 ...

会无限循环。

5. 双向 BFS 不是必须，但很经典

这题普通 BFS 已经能过。

双向 BFS 更适合你在理解 BFS 之后，进一步学习搜索优化。

一句话总结

这题的本质是：

在状态图里，从 0000 出发找到到达 target 的最少旋转次数。

想写标准解：用 普通 BFS
想学搜索优化：用 双向 BFS

752. 打开转盘锁

题目描述

示例 1

示例 2

示例 3

约束

核心思路

先理解：这题为什么是图？

解法一：普通 BFS

思路拆解

如何生成相邻状态？

一步一步写出算法

第一步：先处理边界情况

第二步：把 deadends 放进集合

第三步：定义生成邻居函数

第四步：开始 BFS

第五步：不断扩展队头

第六步：扩展 8 个相邻状态

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：双向 BFS

思路拆解

一步一步写出算法

第一步：准备两个前沿集合

第二步：每轮优先扩展更小的一边

第三步：扩展当前这一层

第四步：更新步数并进入下一轮

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍普通 BFS

第一步：起点

第二步：扩展 0000

第三步：到达目标

面试时最容易错的点

1. 这是最短路题，不是 DFS 题

2. 0 和 9 是连着的

3. 起点也可能是死亡状态

4. 一定要做访问标记

5. 双向 BFS 不是必须，但很经典

一句话总结

推荐你最后记住的标准写法

第二步：把 `deadends` 放进集合

第二步：扩展 `0000`

2. `0` 和 `9` 是连着的