You are given a lock represented by a 4-wheel combination, where each wheel shows a digit from '0' to '9'. Each wheel can be rotated up or down by one digit in a single move (with wraparound: '9' goes to '0' and '0' goes to '9').
The lock starts at the combination "0000". You are given:
deadends: a list of combinations that must never be entered (if you reach one, you are stuck).target: a string representing the lock's target combination.
Your task is to determine the minimum number of moves required to reach target from "0000", without entering any deadend combination. If it is impossible, return -1.
Constraints:
At first glance, you might consider trying all possible sequences of moves to reach the target. However, with 4 wheels and each wheel having 10 positions, there are 10,000 possible combinations. Brute-force search would be highly inefficient, especially with deadends.
The problem is similar to finding the shortest path in a graph, where each node is a lock combination, and edges connect combinations that differ by one wheel move. Since every move has equal cost, the Breadth-First Search (BFS) algorithm is a natural fit—it explores all combinations at each step, ensuring the shortest path is found.
To avoid revisiting combinations and getting stuck in cycles, we'll need a way to track visited combinations. Deadends act as impassable nodes, so we must avoid those as well.
Let's break down the solution step by step:
"0000".queue to manage BFS traversal.set for deadends for O(1) lookup.set to keep track of visited combinations."0000" is a deadend, return -1 immediately.target is "0000", return 0 moves.target combination, return the number of moves taken to reach it.This approach ensures we always find the shortest path, or determine it's impossible.
Let's walk through an example:
Input:
deadends = ["0201","0101","0102","1212","2002"]target = "0202"Step-by-step:
"0000". It's not a deadend.
"0000" (e.g., "1000", "9000", "0100", etc.). Add valid ones to the queue.
"0202" is reached.
6.
The BFS ensures that as soon as we reach "0202", we've found the shortest possible path.
from collections import deque
class Solution:
def openLock(self, deadends, target):
dead = set(deadends)
visited = set('0000')
if '0000' in dead:
return -1
queue = deque([('0000', 0)])
while queue:
node, depth = queue.popleft()
if node == target:
return depth
for i in range(4):
digit = int(node[i])
for move in (-1, 1):
new_digit = (digit + move) % 10
neighbor = node[:i] + str(new_digit) + node[i+1:]
if neighbor not in visited and neighbor not in dead:
visited.add(neighbor)
queue.append((neighbor, depth + 1))
return -1
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
unordered_set<string> visited;
if (dead.count("0000")) return -1;
queue<pair<string, int>> q;
q.push({"0000", 0});
visited.insert("0000");
while (!q.empty()) {
auto [node, depth] = q.front(); q.pop();
if (node == target) return depth;
for (int i = 0; i < 4; ++i) {
char c = node[i];
for (int move : {-1, 1}) {
string neighbor = node;
neighbor[i] = (c - '0' + move + 10) % 10 + '0';
if (!dead.count(neighbor) && !visited.count(neighbor)) {
visited.insert(neighbor);
q.push({neighbor, depth + 1});
}
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Set<String> visited = new HashSet<>();
if (dead.contains("0000")) return -1;
Queue<String> queue = new LinkedList<>();
queue.offer("0000");
visited.add("0000");
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; ++k) {
String node = queue.poll();
if (node.equals(target)) return depth;
for (int i = 0; i < 4; ++i) {
char[] chars = node.toCharArray();
for (int move : new int[]{-1, 1}) {
chars[i] = (char)((chars[i] - '0' + move + 10) % 10 + '0');
String neighbor = new String(chars);
if (!dead.contains(neighbor) && !visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
chars[i] = node.charAt(i); // Reset
}
}
}
depth++;
}
return -1;
}
}
/**
* @param {string[]} deadends
* @param {string} target
* @return {number}
*/
var openLock = function(deadends, target) {
const dead = new Set(deadends);
const visited = new Set(['0000']);
if (dead.has('0000')) return -1;
const queue = [['0000', 0]];
while (queue.length) {
const [node, depth] = queue.shift();
if (node === target) return depth;
for (let i = 0; i < 4; ++i) {
let digit = parseInt(node[i]);
for (let move of [-1, 1]) {
let newDigit = (digit + move + 10) % 10;
let neighbor = node.slice(0, i) + newDigit + node.slice(i + 1);
if (!visited.has(neighbor) && !dead.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, depth + 1]);
}
}
}
}
return -1;
};
Brute-force Approach:
"0000" to "9999").
The BFS ensures we never revisit nodes, and the use of sets keeps lookups fast.
The "Open the Lock" problem is a classic shortest-path challenge on an implicit graph. By modeling each lock combination as a node and each valid move as an edge, we use BFS to efficiently find the minimum moves to the target. Key insights include representing deadends and visited nodes with sets for fast lookups, and using BFS to guarantee the shortest solution. This approach is both efficient and elegant, making it suitable for large search spaces with simple move rules.