752. 打开转盘锁
题目描述
一把密码锁有 4 个转轮，每个转轮上是数字 0 到 9。一次操作只能把某一个转轮向上或向下拨动一格，并且首尾相接：9 再拨一格变成 0，0 反向拨一格变成 9。
锁的当前状态用 4 位数字字符串表示，初始为 "0000"。字符串数组 deadends 列出若干禁止状态，锁一旦处于其中任意一个状态就会卡死，不能再转动。
输入 deadends 和目标状态 target。返回从 "0000" 变到 target 所需的最少操作次数。如果无法到达，返回 -1。
示例 1
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 输出：6
解释：一条可行路线是 0000→1000→1100→1200→1201→1202→0202，共 6 步；更短的路线会经过禁止状态。
示例 2
输入：deadends = ["8888"], target = "0009" 输出：1
解释：把最后一位从 0 反向拨一格得到 9。
示例 3
输入：deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"] target = "8888" 输出：-1
解释：8888 的 8 个相邻状态全是禁止状态，无法到达。
数据范围
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target不会出现在deadends中。target和deadends[i]都只由数字字符组成。
解题思路：广度优先搜索
把每个 4 位状态看成图中的一个节点，每个节点有 8 个邻居（4 个转轮 × 上下两个方向）。从 "0000" 出发做按层 BFS：第 k 层就是恰好需要 k 次旋转才能到达的状态。跳过死亡数字和已访问的状态；第一次在某层遇到 target 时，层号就是答案。
为什么正确
处理第 steps 层时，frontier 恰好包含所有最少需要 steps 次旋转、且路径上不经过死亡数字的状态。
复杂度分析
时间 O(10^4 × 8 × 4)：最多 10^4 个状态，每个生成 8 个邻居、每个邻居拼接长度 4 的字符串。空间 O(10^4)。
易错点
"0000" 本身就是死亡数字时要直接返回 -1。另外要在加入队列时就标记 seen，否则同一状态会被多次入队，状态数会爆炸。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
dead = set(deadends)
if '0000' in dead:
return -1
seen = {'0000'}
frontier = ['0000']
steps = 0
while frontier:
nxt = []
for cur in frontier:
if cur == target:
return steps
for i in range(4):
d = int(cur[i])
for nd in ((d + 1) % 10, (d + 9) % 10):
s = cur[:i] + str(nd) + cur[i + 1:]
if s not in seen and s not in dead:
seen.add(s)
nxt.append(s)
frontier = nxt
steps += 1
return -1class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) {
return -1;
}
Set<String> seen = new HashSet<>();
seen.add("0000");
List<String> frontier = new ArrayList<>();
frontier.add("0000");
int steps = 0;
while (!frontier.isEmpty()) {
List<String> nxt = new ArrayList<>();
for (String cur : frontier) {
if (cur.equals(target)) {
return steps;
}
for (int i = 0; i < 4; i++) {
int d = cur.charAt(i) - '0';
for (int nd : new int[]{(d + 1) % 10, (d + 9) % 10}) {
String s = cur.substring(0, i) + nd + cur.substring(i + 1);
if (!seen.contains(s) && !dead.contains(s)) {
seen.add(s);
nxt.add(s);
}
}
}
}
frontier = nxt;
steps++;
}
return -1;
}
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) {
return -1;
}
unordered_set<string> seen = {"0000"};
vector<string> frontier = {"0000"};
int steps = 0;
while (!frontier.empty()) {
vector<string> nxt;
for (const string& cur : frontier) {
if (cur == target) {
return steps;
}
for (int i = 0; i < 4; i++) {
int d = cur[i] - '0';
for (int nd : {(d + 1) % 10, (d + 9) % 10}) {
string s = cur;
s[i] = '0' + nd;
if (!seen.count(s) && !dead.count(s)) {
seen.insert(s);
nxt.push_back(s);
}
}
}
}
frontier = nxt;
steps++;
}
return -1;
}
};func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, x := range deadends {
dead[x] = true
}
if dead["0000"] {
return -1
}
seen := map[string]bool{"0000": true}
frontier := []string{"0000"}
steps := 0
for len(frontier) > 0 {
nxt := []string{}
for _, cur := range frontier {
if cur == target {
return steps
}
for i := 0; i < 4; i++ {
d := int(cur[i] - '0')
for _, nd := range []int{(d + 1) % 10, (d + 9) % 10} {
s := cur[:i] + string(byte('0'+nd)) + cur[i+1:]
if !seen[s] && !dead[s] {
seen[s] = true
nxt = append(nxt, s)
}
}
}
}
frontier = nxt
steps++
}
return -1
}var openLock = function(deadends, target) {
const dead = new Set(deadends);
if (dead.has('0000')) {
return -1;
}
const seen = new Set(['0000']);
let frontier = ['0000'];
let steps = 0;
while (frontier.length > 0) {
const nxt = [];
for (const cur of frontier) {
if (cur === target) {
return steps;
}
for (let i = 0; i < 4; i++) {
const d = Number(cur[i]);
for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
const s = cur.slice(0, i) + nd + cur.slice(i + 1);
if (!seen.has(s) && !dead.has(s)) {
seen.add(s);
nxt.push(s);
}
}
}
}
frontier = nxt;
steps++;
}
return -1;
};function openLock(deadends: string[], target: string): number {
const dead = new Set(deadends);
if (dead.has('0000')) {
return -1;
}
const seen = new Set(['0000']);
let frontier = ['0000'];
let steps = 0;
while (frontier.length > 0) {
const nxt: string[] = [];
for (const cur of frontier) {
if (cur === target) {
return steps;
}
for (let i = 0; i < 4; i++) {
const d = Number(cur[i]);
for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
const s = cur.slice(0, i) + nd + cur.slice(i + 1);
if (!seen.has(s) && !dead.has(s)) {
seen.add(s);
nxt.push(s);
}
}
}
}
frontier = nxt;
steps++;
}
return -1;
}其他解法
单向广度优先是标准解法，代码简单；双向广度优先在状态空间大、起点和终点都已知时能大幅减少搜索量。
解法 2：双向广度优先搜索 时间 O(10⁴ · 8 · 4)，空间 O(10⁴)
同时从 '0000' 和 target 两端搜索，各自维护一个当前层集合。每次选规模较小的一端扩展一层，生成的邻居如果在另一端的集合里，说明两边相遇，答案是两端已走步数之和。两端共用一个 visited 和 deadends 集合来剪枝。
最坏复杂度不变，但搜索树从一棵深 d 的变成两棵深 d/2 的，实际访问的状态通常少很多。代价是要维护两个集合并处理相遇判断，写法更复杂。
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
dead = set(deadends)
if '0000' in dead or target in dead:
return -1
if target == '0000':
return 0
front, back = {'0000'}, {target}
seen = {'0000', target}
steps = 0
while front and back:
if len(front) > len(back):
front, back = back, front
steps += 1
nxt = set()
for cur in front:
for i in range(4):
d = int(cur[i])
for nd in ((d + 1) % 10, (d + 9) % 10):
s = cur[:i] + str(nd) + cur[i + 1:]
if s in back:
return steps
if s not in seen and s not in dead:
seen.add(s)
nxt.add(s)
front = nxt
return -1class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000") || dead.contains(target)) return -1;
if (target.equals("0000")) return 0;
Set<String> front = new HashSet<>(), back = new HashSet<>(), seen = new HashSet<>();
front.add("0000");
back.add(target);
seen.add("0000");
seen.add(target);
int steps = 0;
while (!front.isEmpty() && !back.isEmpty()) {
if (front.size() > back.size()) {
Set<String> t = front;
front = back;
back = t;
}
steps++;
Set<String> nxt = new HashSet<>();
for (String cur : front) {
char[] cs = cur.toCharArray();
for (int i = 0; i < 4; i++) {
char orig = cs[i];
int d = orig - '0';
for (int nd : new int[]{(d + 1) % 10, (d + 9) % 10}) {
cs[i] = (char) ('0' + nd);
String s = new String(cs);
if (back.contains(s)) return steps;
if (!seen.contains(s) && !dead.contains(s)) {
seen.add(s);
nxt.add(s);
}
}
cs[i] = orig;
}
}
front = nxt;
}
return -1;
}
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000") || dead.count(target)) return -1;
if (target == "0000") return 0;
unordered_set<string> front = {"0000"}, back = {target};
unordered_set<string> seen = {"0000", target};
int steps = 0;
while (!front.empty() && !back.empty()) {
if (front.size() > back.size()) swap(front, back);
steps++;
unordered_set<string> nxt;
for (const string& cur : front) {
for (int i = 0; i < 4; i++) {
int d = cur[i] - '0';
for (int nd : {(d + 1) % 10, (d + 9) % 10}) {
string s = cur;
s[i] = '0' + nd;
if (back.count(s)) return steps;
if (!seen.count(s) && !dead.count(s)) {
seen.insert(s);
nxt.insert(s);
}
}
}
}
front = move(nxt);
}
return -1;
}
};func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, d := range deadends {
dead[d] = true
}
if dead["0000"] || dead[target] {
return -1
}
if target == "0000" {
return 0
}
front := map[string]bool{"0000": true}
back := map[string]bool{target: true}
seen := map[string]bool{"0000": true, target: true}
steps := 0
for len(front) > 0 && len(back) > 0 {
if len(front) > len(back) {
front, back = back, front
}
steps++
nxt := map[string]bool{}
for cur := range front {
cs := []byte(cur)
for i := 0; i < 4; i++ {
orig := cs[i]
d := int(orig - '0')
for _, nd := range []int{(d + 1) % 10, (d + 9) % 10} {
cs[i] = byte('0' + nd)
s := string(cs)
if back[s] {
return steps
}
if !seen[s] && !dead[s] {
seen[s] = true
nxt[s] = true
}
}
cs[i] = orig
}
}
front = nxt
}
return -1
}var openLock = function(deadends, target) {
const dead = new Set(deadends);
if (dead.has('0000') || dead.has(target)) return -1;
if (target === '0000') return 0;
let front = new Set(['0000']), back = new Set([target]);
const seen = new Set(['0000', target]);
let steps = 0;
while (front.size > 0 && back.size > 0) {
if (front.size > back.size) [front, back] = [back, front];
steps++;
const nxt = new Set();
for (const cur of front) {
for (let i = 0; i < 4; i++) {
const d = cur.charCodeAt(i) - 48;
for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
const s = cur.slice(0, i) + nd + cur.slice(i + 1);
if (back.has(s)) return steps;
if (!seen.has(s) && !dead.has(s)) {
seen.add(s);
nxt.add(s);
}
}
}
}
front = nxt;
}
return -1;
};function openLock(deadends: string[], target: string): number {
const dead = new Set<string>(deadends);
if (dead.has('0000') || dead.has(target)) return -1;
if (target === '0000') return 0;
let front = new Set<string>(['0000']), back = new Set<string>([target]);
const seen = new Set<string>(['0000', target]);
let steps = 0;
while (front.size > 0 && back.size > 0) {
if (front.size > back.size) [front, back] = [back, front];
steps++;
const nxt = new Set<string>();
for (const cur of front) {
for (let i = 0; i < 4; i++) {
const d = cur.charCodeAt(i) - 48;
for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
const s = cur.slice(0, i) + nd + cur.slice(i + 1);
if (back.has(s)) return steps;
if (!seen.has(s) && !dead.has(s)) {
seen.add(s);
nxt.add(s);
}
}
}
}
front = nxt;
}
return -1;
}