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
- BFS over the state space of 10 000 combinations, starting from
"0000". - Neighbours are the eight states reachable by turning one dial up or down (with wraparound).
- Deadends are simply never enqueued, which prunes the search.
- 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 - 1must become9, 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.