LeetCode 752 - Open the Lock

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Breadth-First Search

Solution

Problem Understanding

The problem presents a lock with four wheels, each wheel labeled from '0' to '9', which can rotate forwards or backwards. The lock starts at '0000', and we are given a list of "deadends," which are lock states that will cause the lock to freeze if reached. The goal is to determine the minimum number of wheel turns required to reach a specified target state without passing through any deadends. If it is impossible to reach the target due to deadends blocking all paths, we must return -1.

The input consists of two main components: a list of deadends and a string target. Each deadend and the target are exactly 4-character strings representing the lock wheels. Constraints guarantee that target will never be a deadend and that the number of deadends is manageable (up to 500). The problem involves searching through the state space of the lock, which has a maximum of 10,000 states (0000 to 9999).

Edge cases include starting at a deadend, the target being only one move away, or deadends surrounding the starting state entirely, making it impossible to proceed.

Approaches

A brute-force approach would attempt to explore all possible sequences of moves from '0000' until reaching the target, while avoiding deadends. This could be implemented with a recursive depth-first search, exploring every possible turn of every wheel. While it is correct, the complexity is exponential in the number of moves, which makes it impractical for this problem because it could explore nearly all 10,000 possible states in the worst case.

The key insight is that the problem can be modeled as a shortest-path search in an unweighted graph, where nodes are lock states, and edges connect states that differ by a single wheel turn. Using Breadth-First Search (BFS) ensures that we find the minimum number of turns to reach the target because BFS explores all states at distance d from the start before exploring states at distance d+1. We also need a visited set to avoid revisiting states and a deadends set to prune invalid paths.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^L * L!)	O(10^L)	Recursive DFS exploring all sequences of moves; exponential and impractical
Optimal	O(10^L * L)	O(10^L)	BFS from `'0000'` avoiding deadends; guarantees shortest path

Here, L is 4, the number of wheels.

Algorithm Walkthrough

Convert the deadends list into a set for O(1) membership checks.
Check if the starting state '0000' is in deadends. If so, return -1 immediately because we cannot start.
Initialize a queue with the starting state '0000' and a counter for moves.
Initialize a visited set to track states that have already been explored.
While the queue is not empty, process all states at the current level of BFS:
Dequeue a state and check if it matches the target. If it does, return the number of moves taken to reach it.
For each wheel position, generate two new states by incrementing or decrementing the digit (wrap around 0-9). For example, turning '0' backwards gives '9'.
If the generated state is not in deadends and has not been visited, add it to the queue and mark it as visited.
Increment the move counter after processing all states at the current BFS level.
If the queue becomes empty without finding the target, return -1.

Why it works: BFS guarantees the shortest path in an unweighted graph because it explores all states at distance d before states at distance d+1. Using a visited set ensures we do not revisit states and prevents infinite loops caused by cycling through wheel positions.

Python Solution

from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead_set = set(deadends)
        if '0000' in dead_set:
            return -1
        
        queue = deque([('0000', 0)])  # state, steps
        visited = set('0000')
        
        while queue:
            state, steps = queue.popleft()
            if state == target:
                return steps
            
            for i in range(4):
                digit = int(state[i])
                for move in (-1, 1):
                    new_digit = (digit + move) % 10
                    new_state = state[:i] + str(new_digit) + state[i+1:]
                    if new_state not in dead_set and new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_state, steps + 1))
        
        return -1

This Python implementation initializes the deadends as a set for efficient lookups and uses a queue to implement BFS. Each state is expanded by turning every wheel forward and backward, skipping deadends and visited states. The steps variable tracks the number of moves, which increments naturally with BFS levels.

Go Solution

package main

import "container/list"

func openLock(deadends []string, target string) int {
    deadSet := make(map[string]bool)
    for _, d := range deadends {
        deadSet[d] = true
    }
    if deadSet["0000"] {
        return -1
    }

    queue := list.New()
    queue.PushBack([2]interface{}{"0000", 0})
    visited := map[string]bool{"0000": true}

    for queue.Len() > 0 {
        front := queue.Remove(queue.Front()).([2]interface{})
        state := front[0].(string)
        steps := front[1].(int)

        if state == target {
            return steps
        }

        for i := 0; i < 4; i++ {
            digit := int(state[i] - '0')
            for _, move := range []int{-1, 1} {
                newDigit := (digit + move + 10) % 10
                newState := state[:i] + string('0'+newDigit) + state[i+1:]
                if !deadSet[newState] && !visited[newState] {
                    visited[newState] = true
                    queue.PushBack([2]interface{}{newState, steps + 1})
                }
            }
        }
    }
    return -1
}

The Go solution mirrors the Python BFS approach, using a list.List as a queue and a map to track visited states. Go requires explicit type conversions when handling queue elements and string-digit manipulations.

Worked Examples

Example 1:

Deadends: ["0201","0101","0102","1212","2002"], Target: "0202"

BFS expands:

Step	Queue States	Notes
0	["0000"]	Start
1	["1000","9000","0100","0900","0010","0090","0001","0009"]	All neighbors of "0000"
2	["1000", "9000", ...]	Continue BFS avoiding deadends
6	["0202"]	Target reached, 6 moves

Example 2:

Deadends: ["8888"], Target: "0009"

One move: "0000" -> "0009", result 1.

Example 3:

Deadends: ["8887","8889","8878","8898","8788","8988","7888","9888"], Target: "8888"

All paths to "8888" blocked, return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(10^4 * 4)	Each of the 10,000 possible states may be visited once, generating 8 neighbors each (4 wheels * 2 directions)
Space	O(10^4)	Visited set and queue can hold up to 10,000 states

Since L=4 wheels, the search space is small enough to allow BFS.

Test Cases

# Provided examples
assert Solution().openLock(["0201","0101","0102","1212","2002"], "0202") == 6  # normal case
assert Solution().openLock(["8888"], "0009") == 1  # one move away
assert Solution().openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888") == -1  # unreachable

# Edge cases
assert Solution().openLock(["0000"], "8888") == -1  # start blocked
assert Solution().openLock([], "0000") == 0  # target is start
assert Solution().openLock([], "0001") == 1  # single move

Test	Why
Provided examples	Validates correctness against problem statement
Start is deadend	Ensures immediate return -1 is handled
Target is start	Ensures zero moves is returned correctly
Single move target	Ensures minimal move calculation is correct