⚡Flashcard Drill➔
NeetCode #573LC-752MediumGraphsNC 250
← Back to All Problems

#573 · #752 · Open the Lock(打开转盘锁)

📌 Problem Statement & Constraints

A lock has four circular dials with digits 0-9. Starting from "0000", each move turns one dial one step in either direction. Given a list of deadends, return the minimum moves to reach target, or -1 if impossible. Constraints: 1 <= deadends.length <= 500, deadends[i].length == 4, target.length == 4.

💡 Core Algorithmic Approaches

  1. BFS over the state space of 10 000 combinations, starting from "0000".
  2. Neighbours are the eight states reachable by turning one dial up or down (with wraparound).
  3. Deadends are simply never enqueued, which prunes the search.
  4. The first time the target is dequeued (or generated), the distance is minimal.

💻 Benchmark Python3 Implementation

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        from collections import deque
        dead = set(deadends)
        if "0000" in dead:
            return -1                      # the start itself is blocked
        q = deque([("0000", 0)])
        seen = {"0000"}
        while q:
            state, dist = q.popleft()
            if state == target:
                return dist
            for i in range(4):
                d = int(state[i])
                for delta in (-1, 1):
                    nd = (d + delta) % 10  # wraparound
                    nxt = state[:i] + str(nd) + state[i + 1:]
                    if nxt not in seen and nxt not in dead:
                        seen.add(nxt)
                        q.append((nxt, dist + 1))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(10^4 * 8) = O(1) in the state space size: at most 10 000 states.
💾 Space Complexity
O(10^4) for the visited set and the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the wraparound: 0 - 1 must become 9, hence the % 10.
  • Not checking whether "0000" is a deadend: the start itself could be blocked.
  • Using a DFS: it does not guarantee the shortest sequence.
  • Marking visited when dequeuing instead of when enqueuing: the same state could be enqueued many times, bloating the queue.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems