Open the Lock
Problem
A 4-wheel combination lock starts at "0000". Each move turns one wheel up or down by one (with wraparound 0↔9). Given a list of forbidden deadend states, return the minimum moves needed to reach target, or −1 if impossible.
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6from collections import deque
def open_lock(deadends, target):
dead = set(deadends)
if "0000" in dead:
return -1
if target == "0000":
return 0
q = deque([("0000", 0)])
seen = {"0000"}
while q:
s, d = q.popleft()
for i in range(4):
for delta in (-1, 1):
nd = (int(s[i]) + delta) % 10
nxt = s[:i] + str(nd) + s[i+1:]
if nxt == target:
return d + 1
if nxt in dead or nxt in seen:
continue
seen.add(nxt)
q.append((nxt, d + 1))
return -1function openLock(deadends, target) {
const dead = new Set(deadends);
if (dead.has("0000")) return -1;
if (target === "0000") return 0;
const q = [["0000", 0]];
const seen = new Set(["0000"]);
while (q.length) {
const [s, d] = q.shift();
for (let i = 0; i < 4; i++) {
for (const delta of [-1, 1]) {
const nd = (Number(s[i]) + delta + 10) % 10;
const nxt = s.slice(0, i) + nd + s.slice(i + 1);
if (nxt === target) return d + 1;
if (dead.has(nxt) || seen.has(nxt)) continue;
seen.add(nxt);
q.push([nxt, d + 1]);
}
}
}
return -1;
}class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
if (target.equals("0000")) return 0;
Deque<String> q = new ArrayDeque<>();
Set<String> seen = new HashSet<>();
q.offer("0000"); seen.add("0000");
int steps = 0;
while (!q.isEmpty()) {
steps++;
int sz = q.size();
for (int k = 0; k < sz; k++) {
String s = q.poll();
for (int i = 0; i < 4; i++) {
int c = s.charAt(i) - '0';
for (int delta : new int[]{-1, 1}) {
int nd = (c + delta + 10) % 10;
String nxt = s.substring(0, i) + nd + s.substring(i + 1);
if (nxt.equals(target)) return steps;
if (dead.contains(nxt) || seen.contains(nxt)) continue;
seen.add(nxt);
q.offer(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")) return -1;
if (target == "0000") return 0;
queue<string> q;
unordered_set<string> seen;
q.push("0000"); seen.insert("0000");
int steps = 0;
while (!q.empty()) {
steps++;
int sz = q.size();
for (int k = 0; k < sz; k++) {
string s = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int c = s[i] - '0';
for (int delta : {-1, 1}) {
int nd = (c + delta + 10) % 10;
string nxt = s; nxt[i] = '0' + nd;
if (nxt == target) return steps;
if (dead.count(nxt) || seen.count(nxt)) continue;
seen.insert(nxt);
q.push(nxt);
}
}
}
}
return -1;
}
};Explanation
Think of every 4-digit lock state as a node in a graph. From any state you can reach 8 neighbors: each of the 4 wheels can turn up or down by one. Since each move costs the same, the fewest moves to the target is a shortest path, and breadth-first search finds it.
We start a BFS from "0000", exploring states level by level. The first time we reach the target, the level number is the minimum number of moves. A seen set stops us from revisiting states, and the dead set lets us skip forbidden deadends.
For each state we loop over the 4 wheels and both directions delta of -1 and +1, using % 10 so that 0 wraps to 9 and 9 wraps to 0. Each fresh, non-dead, unseen neighbor is queued with distance d + 1.
Two quick exits up front: if "0000" is itself a deadend we return -1, and if the target is "0000" we return 0.
Example: target "0202" with the given deadends. BFS spreads out wheel by wheel and first touches "0202" after a 6-turn path like 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202, so the answer is 6. If the queue empties without reaching the target, it is impossible and we return -1.