LeetCode 752: Open the Lock (BFS Shortest Path on State Graph)
LeetCode 752BFSGraphShortest PathToday we solve LeetCode 752 - Open the Lock.
Source: https://leetcode.com/problems/open-the-lock/
English
Problem Summary
You start at lock state 0000. Each move rotates one wheel forward or backward by one. Some states are deadends and cannot be entered. Find the minimum number of moves to reach target, or return -1.
Key Insight
This is an unweighted shortest-path problem on an implicit graph: each 4-digit state has up to 8 neighbors. Use BFS level by level to guarantee the first time we pop target is the minimum moves.
Brute Force and Limitations
DFS/backtracking explores deep branches without shortest-path guarantee and can explode exponentially. BFS with a visited set prevents repeated states and is optimal for unweighted graphs.
Optimal Algorithm Steps
1) Put all deadends into a hash set.
2) If 0000 is dead, return -1; if target is 0000, return 0.
3) Start BFS queue from 0000, mark visited.
4) For each state, generate 8 neighbors by turning each wheel ±1 (with wraparound).
5) Skip dead/visited states; enqueue valid states.
6) Count BFS levels; when target appears, return level distance.
Complexity Analysis
Time: O(10^4) worst case, each state expands at most once with 8 neighbors.
Space: O(10^4) for deadend set + visited + queue.
Common Pitfalls
- Forgetting wraparound (9 -> 0, 0 -> 9).
- Not checking deadend at start state.
- Marking visited too late, causing duplicate enqueues.
- Using recursion/DFS and expecting shortest steps.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
if ("0000".equals(target)) return 0;
Queue<String> q = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
q.offer("0000");
visited.add("0000");
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(target)) return steps;
for (String nxt : neighbors(cur)) {
if (dead.contains(nxt) || visited.contains(nxt)) continue;
visited.add(nxt);
q.offer(nxt);
}
}
steps++;
}
return -1;
}
private List<String> neighbors(String s) {
List<String> res = new ArrayList<>(8);
char[] arr = s.toCharArray();
for (int i = 0; i < 4; i++) {
char old = arr[i];
arr[i] = old == '9' ? '0' : (char)(old + 1);
res.add(new String(arr));
arr[i] = old == '0' ? '9' : (char)(old - 1);
res.add(new String(arr));
arr[i] = old;
}
return res;
}
}func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, d := range deadends {
dead[d] = true
}
if dead["0000"] {
return -1
}
if target == "0000" {
return 0
}
visited := map[string]bool{"0000": true}
q := []string{"0000"}
steps := 0
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
cur := q[0]
q = q[1:]
if cur == target {
return steps
}
for _, nxt := range neighbors(cur) {
if dead[nxt] || visited[nxt] {
continue
}
visited[nxt] = true
q = append(q, nxt)
}
}
steps++
}
return -1
}
func neighbors(s string) []string {
b := []byte(s)
ans := make([]string, 0, 8)
for i := 0; i < 4; i++ {
old := b[i]
if old == '9' {
b[i] = '0'
} else {
b[i] = old + 1
}
ans = append(ans, string(b))
if old == '0' {
b[i] = '9'
} else {
b[i] = old - 1
}
ans = append(ans, string(b))
b[i] = old
}
return ans
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
if (target == "0000") return 0;
queue<string> q;
unordered_set<string> vis;
q.push("0000");
vis.insert("0000");
int steps = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front(); q.pop();
if (cur == target) return steps;
for (string nxt : neighbors(cur)) {
if (dead.count(nxt) || vis.count(nxt)) continue;
vis.insert(nxt);
q.push(nxt);
}
}
steps++;
}
return -1;
}
private:
vector<string> neighbors(string s) {
vector<string> res;
res.reserve(8);
for (int i = 0; i < 4; ++i) {
char old = s[i];
s[i] = (old == '9') ? '0' : old + 1;
res.push_back(s);
s[i] = (old == '0') ? '9' : old - 1;
res.push_back(s);
s[i] = old;
}
return res;
}
};from collections import deque
from typing import List
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
dead = set(deadends)
if "0000" in dead:
return -1
if target == "0000":
return 0
q = deque(["0000"])
visited = {"0000"}
steps = 0
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == target:
return steps
for nxt in self.neighbors(cur):
if nxt in dead or nxt in visited:
continue
visited.add(nxt)
q.append(nxt)
steps += 1
return -1
def neighbors(self, s: str):
arr = list(s)
for i in range(4):
old = arr[i]
arr[i] = '0' if old == '9' else chr(ord(old) + 1)
yield ''.join(arr)
arr[i] = '9' if old == '0' else chr(ord(old) - 1)
yield ''.join(arr)
arr[i] = oldvar openLock = function(deadends, target) {
const dead = new Set(deadends);
if (dead.has('0000')) return -1;
if (target === '0000') return 0;
const visited = new Set(['0000']);
const queue = ['0000'];
let head = 0;
let steps = 0;
while (head < queue.length) {
const size = queue.length - head;
for (let i = 0; i < size; i++) {
const cur = queue[head++];
if (cur === target) return steps;
for (const nxt of neighbors(cur)) {
if (dead.has(nxt) || visited.has(nxt)) continue;
visited.add(nxt);
queue.push(nxt);
}
}
steps++;
}
return -1;
};
function neighbors(s) {
const arr = s.split('');
const res = [];
for (let i = 0; i < 4; i++) {
const old = arr[i];
arr[i] = old === '9' ? '0' : String.fromCharCode(old.charCodeAt(0) + 1);
res.push(arr.join(''));
arr[i] = old === '0' ? '9' : String.fromCharCode(old.charCodeAt(0) - 1);
res.push(arr.join(''));
arr[i] = old;
}
return res;
}中文
题目概述
你从锁状态 0000 出发。每次可以把任意一位拨轮向上或向下拨一格。某些状态是死亡状态，不能进入。求到达目标 target 的最少步数；无法到达返回 -1。
核心思路
这是一个无权图最短路问题：每个四位字符串状态最多有 8 个邻居。按层进行 BFS，首次访问到目标时对应的层数就是最短步数。
暴力解法与不足
DFS/回溯会优先走深路径，不保证最短，并且分支数很大。BFS + visited 可以避免重复扩展，同时天然保证最短路。
最优算法步骤
1）把 deadends 放入哈希集合。
2）若 0000 是 deadend，直接返回 -1；若目标就是 0000 返回 0。
3）从 0000 入队并标记 visited。
4）每次弹出状态，生成 8 个邻居（每个拨轮 ±1，含环绕）。
5）跳过 dead/visited 状态，其余入队。
6）按层计步，遇到 target 即返回步数。
复杂度分析
时间复杂度：最坏 O(10^4)，每个状态至多扩展一次，每次常数 8 个邻居。
空间复杂度：O(10^4)。
常见陷阱
- 忘记拨轮环绕（9 -> 0、0 -> 9）。
- 起点死锁未提前判断。
- visited 标记过晚，导致重复入队。
- 用 DFS 期待得到最短步数。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
if ("0000".equals(target)) return 0;
Queue<String> q = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
q.offer("0000");
visited.add("0000");
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(target)) return steps;
for (String nxt : neighbors(cur)) {
if (dead.contains(nxt) || visited.contains(nxt)) continue;
visited.add(nxt);
q.offer(nxt);
}
}
steps++;
}
return -1;
}
private List<String> neighbors(String s) {
List<String> res = new ArrayList<>(8);
char[] arr = s.toCharArray();
for (int i = 0; i < 4; i++) {
char old = arr[i];
arr[i] = old == '9' ? '0' : (char)(old + 1);
res.add(new String(arr));
arr[i] = old == '0' ? '9' : (char)(old - 1);
res.add(new String(arr));
arr[i] = old;
}
return res;
}
}func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, d := range deadends {
dead[d] = true
}
if dead["0000"] {
return -1
}
if target == "0000" {
return 0
}
visited := map[string]bool{"0000": true}
q := []string{"0000"}
steps := 0
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
cur := q[0]
q = q[1:]
if cur == target {
return steps
}
for _, nxt := range neighbors(cur) {
if dead[nxt] || visited[nxt] {
continue
}
visited[nxt] = true
q = append(q, nxt)
}
}
steps++
}
return -1
}
func neighbors(s string) []string {
b := []byte(s)
ans := make([]string, 0, 8)
for i := 0; i < 4; i++ {
old := b[i]
if old == '9' {
b[i] = '0'
} else {
b[i] = old + 1
}
ans = append(ans, string(b))
if old == '0' {
b[i] = '9'
} else {
b[i] = old - 1
}
ans = append(ans, string(b))
b[i] = old
}
return ans
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
if (target == "0000") return 0;
queue<string> q;
unordered_set<string> vis;
q.push("0000");
vis.insert("0000");
int steps = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front(); q.pop();
if (cur == target) return steps;
for (string nxt : neighbors(cur)) {
if (dead.count(nxt) || vis.count(nxt)) continue;
vis.insert(nxt);
q.push(nxt);
}
}
steps++;
}
return -1;
}
private:
vector<string> neighbors(string s) {
vector<string> res;
res.reserve(8);
for (int i = 0; i < 4; ++i) {
char old = s[i];
s[i] = (old == '9') ? '0' : old + 1;
res.push_back(s);
s[i] = (old == '0') ? '9' : old - 1;
res.push_back(s);
s[i] = old;
}
return res;
}
};from collections import deque
from typing import List
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
dead = set(deadends)
if "0000" in dead:
return -1
if target == "0000":
return 0
q = deque(["0000"])
visited = {"0000"}
steps = 0
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == target:
return steps
for nxt in self.neighbors(cur):
if nxt in dead or nxt in visited:
continue
visited.add(nxt)
q.append(nxt)
steps += 1
return -1
def neighbors(self, s: str):
arr = list(s)
for i in range(4):
old = arr[i]
arr[i] = '0' if old == '9' else chr(ord(old) + 1)
yield ''.join(arr)
arr[i] = '9' if old == '0' else chr(ord(old) - 1)
yield ''.join(arr)
arr[i] = oldvar openLock = function(deadends, target) {
const dead = new Set(deadends);
if (dead.has('0000')) return -1;
if (target === '0000') return 0;
const visited = new Set(['0000']);
const queue = ['0000'];
let head = 0;
let steps = 0;
while (head < queue.length) {
const size = queue.length - head;
for (let i = 0; i < size; i++) {
const cur = queue[head++];
if (cur === target) return steps;
for (const nxt of neighbors(cur)) {
if (dead.has(nxt) || visited.has(nxt)) continue;
visited.add(nxt);
queue.push(nxt);
}
}
steps++;
}
return -1;
};
function neighbors(s) {
const arr = s.split('');
const res = [];
for (let i = 0; i < 4; i++) {
const old = arr[i];
arr[i] = old === '9' ? '0' : String.fromCharCode(old.charCodeAt(0) + 1);
res.push(arr.join(''));
arr[i] = old === '0' ? '9' : String.fromCharCode(old.charCodeAt(0) - 1);
res.push(arr.join(''));
arr[i] = old;
}
return res;
}
Comments