Open the Lock

DFS Backtracking — Exploring the Lock State Space — Watch how DFS explores paths depth-first, hitting deadends and backtracking before eventually finding the target. The visited set grows and shrinks as we backtrack.

class Solution {
public:
    int minMoves;

    void dfs(string& state, string& target,
             unordered_set<string>& dead,
             unordered_set<string>& visited, int depth) {
        if (state == target) {
            minMoves = min(minMoves, depth);
            return;
        }
        if (depth >= minMoves) return;

        for (int i = 0; i < 4; i++) {
            for (int delta : {1, -1}) {
                string next = state;
                next[i] = '0' + (state[i] - '0' + delta + 10) % 10;
                if (!dead.count(next) && !visited.count(next)) {
                    visited.insert(next);
                    dfs(next, target, dead, visited, depth + 1);
                    visited.erase(next);
                }
            }
        }
    }

    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;

        minMoves = INT_MAX;
        unordered_set<string> visited;
        visited.insert("0000");
        string start = "0000";
        dfs(start, target, dead, visited, 0);

        return minMoves == INT_MAX ? -1 : minMoves;
    }
};

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

        min_moves = [float('inf')]

        def dfs(state: str, depth: int, visited: set) -> None:
            if state == target:
                min_moves[0] = min(min_moves[0], depth)
                return
            if depth >= min_moves[0]:
                return

            for i in range(4):
                d = int(state[i])
                for delta in [1, -1]:
                    new_digit = (d + delta) % 10
                    new_state = state[:i] + str(new_digit) + state[i + 1:]
                    if new_state not in visited and new_state not in dead:
                        visited.add(new_state)
                        dfs(new_state, depth + 1, visited)
                        visited.remove(new_state)

        visited = {"0000"}
        dfs("0000", 0, visited)
        return min_moves[0] if min_moves[0] != float('inf') else -1

import java.util.*;

class Solution {
    private int minMoves = Integer.MAX_VALUE;

    private void dfs(String state, String target,
                     Set<String> dead, Set<String> visited, int depth) {
        if (state.equals(target)) {
            minMoves = Math.min(minMoves, depth);
            return;
        }
        if (depth >= minMoves) return;

        for (int i = 0; i < 4; i++) {
            for (int delta : new int[]{1, -1}) {
                char[] chars = state.toCharArray();
                chars[i] = (char) ('0' + (chars[i] - '0' + delta + 10) % 10);
                String next = new String(chars);
                if (!dead.contains(next) && !visited.contains(next)) {
                    visited.add(next);
                    dfs(next, target, dead, visited, depth + 1);
                    visited.remove(next);
                }
            }
        }
    }

    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;

        minMoves = Integer.MAX_VALUE;
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        dfs("0000", target, dead, visited, 0);

        return minMoves == Integer.MAX_VALUE ? -1 : minMoves;
    }
}

BFS — Level-by-Level Exploration of Lock States — Watch how BFS systematically explores all states at distance d before moving to distance d+1, guaranteeing the shortest path is found first.

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> visited;
        q.push("0000");
        visited.insert("0000");
        int moves = 0;

        while (!q.empty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                string state = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    for (int delta : {1, -1}) {
                        string next = state;
                        next[i] = '0' + (state[i] - '0' + delta + 10) % 10;
                        if (next == target) return moves + 1;
                        if (!dead.count(next) && !visited.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                }
            }
            moves++;
        }

        return -1;
    }
};

from collections import deque

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

        queue = deque(["0000"])
        visited = {"0000"}
        moves = 0

        while queue:
            size = len(queue)
            for _ in range(size):
                state = queue.popleft()
                for i in range(4):
                    d = int(state[i])
                    for delta in [1, -1]:
                        new_digit = (d + delta) % 10
                        new_state = state[:i] + str(new_digit) + state[i + 1:]
                        if new_state == target:
                            return moves + 1
                        if new_state not in visited and new_state not in dead:
                            visited.add(new_state)
                            queue.append(new_state)
            moves += 1

        return -1

import java.util.*;

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;

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        visited.add("0000");
        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                String state = queue.poll();
                for (int i = 0; i < 4; i++) {
                    for (int delta : new int[]{1, -1}) {
                        char[] chars = state.toCharArray();
                        chars[i] = (char) ('0' + (chars[i] - '0' + delta + 10) % 10);
                        String next = new String(chars);
                        if (next.equals(target)) return moves + 1;
                        if (!dead.contains(next) && !visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                    }
                }
            }
            moves++;
        }

        return -1;
    }
}