Open the Lock — Editorial

Opening the reading…

Intuitionwhy the lock is a shortest-path problem

A lock code is a state, and one legal move changes exactly one wheel by one slot. Therefore two codes are connected when they differ in one position by one circular step. The task asks for the fewest moves from 0000 to the target, which is exactly the shortest-path distance between two states in an unweighted graph.

Breadth-first search explores every code reachable in zero moves, then every code reachable in one move, then every code reachable in two moves, and so on. The first time it reaches the target, no shorter route could have been skipped. Deadends are simply states that must never be entered, while a deadend at 0000 prevents the search from starting at all.

One code has eight possible one-move neighbors, before blocked or already visited states are removed.

Approach

Put every deadend into a hash set so checking whether a generated code is blocked takes constant expected time; scanning the deadend list for every neighbor would add unnecessary repeated work.

Check whether 0000 is a deadend before starting the search, because entering the initial blocked state means no move is legal and the answer is immediately -1.

Return 0 when the target is 0000, because the lock already shows the target and BFS should not perform a move just to rediscover the starting state.

Insert 0000 into the queue and visited set; marking it when enqueued prevents a later route from adding the same code again before it is removed from the queue.

Process the queue one layer at a time and increase the move count once per layer, because every code in that layer is reached with the same minimum number of moves.

For each code, try increasing and decreasing each of its four digits, restoring the original digit after each trial; this enumerates exactly the eight legal one-move states without permanently changing the current code.

For each candidate, return the current layer distance if it is the target, otherwise enqueue it only when it is neither a deadend nor visited; when the queue empties, no permitted path exists, so return -1.

Complexitybounded state space, not just the number of deadends

MEASURE	BOUND	WHY
Time	O(N + m)	Building the deadend set processes m codes. BFS removes each reachable code from the queue once and tests eight neighbors, so the constant eight does not multiply the asymptotic bound; each code is also inserted into visited at most once.
Space	O(N + m) extra	The deadend set, visited set, and queue together can hold O(N + m) entries in the worst case. The returned integer is not output storage, and there is no separate output container; for this problem N is fixed at 10^4.

N is the number of possible lock codes, N = 10^4 for four decimal wheels, and m is the number of deadends. Each state has exactly eight candidate moves.

Annotated solutionC++ · layered BFS · complete judge-ready implementation

CPPLayered BFS that generates and filters all eight one-move neighbors of each code.

#include <queue>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deadSet(deadends.begin(), deadends.end());

        if (deadSet.count("0000")) {
            return -1;
        }
        if (target == "0000") {
            return 0;
        }

        queue<string> q;
        unordered_set<string> visited;
        q.push("0000");
        visited.insert("0000");

        int steps = 0;
        while (!q.empty()) {
            int levelSize = static_cast<int>(q.size());
            ++steps;

            for (int i = 0; i < levelSize; ++i) {
                string cur = q.front();
                q.pop();

                for (int j = 0; j < 4; ++j) {
                    char original = cur[j];

                    for (int delta : {-1, 1}) {
                        char nextDigit = static_cast<char>(
                            (original - '0' + delta + 10) % 10 + '0'
                        );
                        cur[j] = nextDigit;

                        if (cur == target) {
                            return steps;
                        }

                        if (!visited.count(cur) && !deadSet.count(cur)) {
                            visited.insert(cur);
                            q.push(cur);
                        }
                    }

                    cur[j] = original;
                }
            }
        }

        return -1;
    }
};

The levelSize snapshot is the line that gives steps its meaning: every code removed during this loop was reached with the same number of moves. The restore assignment is equally important because each of the eight trials must start from the unchanged current code, not from the digit modified by the previous trial.