{x}
blog image

Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.

 

Constraints:

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • target will not be in the list deadends.
  • target and deadends[i] consist of digits only.

Solution Explanation for LeetCode 752: Open the Lock

This problem asks for the minimum number of turns to open a lock given a list of deadends. The solution employs a breadth-first search (BFS) algorithm, enhanced in different ways across the provided solutions.

Core Logic (All Solutions):

All solutions utilize BFS to explore the state space of the lock. The core idea is:

  1. Start Node: Begin at state "0000".
  2. Neighbors: For each state, generate all possible next states by rotating one wheel one position in either direction (clockwise or counter-clockwise).
  3. Queue: Use a queue to manage states to explore.
  4. Visited Set: Maintain a set to track visited states (to prevent cycles).
  5. Deadends Set: Maintain a set of deadend combinations.
  6. Iteration: Repeatedly dequeue a state from the queue, generate its neighbors, check if they are valid (not deadends and not visited), enqueue valid neighbors, and increment the distance (number of turns).
  7. Target Found: If the target state is encountered, return the current distance.
  8. No Solution: If the queue becomes empty without finding the target, return -1.

Solution 1: Basic BFS

This solution implements a straightforward BFS. It uses a set to track visited states and a deque (double-ended queue) for the BFS queue. The next function efficiently generates all neighbors of a given state.

Time Complexity: O(104), which is linear in the total number of possible states of the lock (10,000, from 0000 to 9999). In the worst case, we visit all possible states.

Space Complexity: O(104) in the worst case, proportional to the number of visited states.

Solution 2: Bidirectional BFS

This solution optimizes BFS by using bidirectional search. It starts searches from both the initial state ("0000") and the target state simultaneously. This significantly reduces the search space, especially when the solution is far from the starting state. It maintains two maps (m1, m2) to store distances from the start and target respectively. When a state is encountered in both searches, the minimum total distance is found.

Time Complexity: O(102), significantly better than the unidirectional BFS in many cases, as it explores a much smaller portion of the state space. Worst case still O(104).

Space Complexity: O(104) in the worst case, as we need to store distances for the visited states in both directions.

Solution 3: A Search (Heuristic)*

This solution employs A* search, which is a more sophisticated graph search algorithm that uses a heuristic function to guide the search. The heuristic function (f) estimates the remaining distance from a given state to the target state. It uses the Manhattan distance of each digit between the current and target state. This heuristic is admissible and consistent. This enables the algorithm to find the shortest path more efficiently than basic BFS. It uses a priority queue (heapq in Python) to prioritize states with lower estimated total costs.

Time Complexity: Difficult to precisely analyze, but it should be better than basic BFS in practice due to the heuristic guidance. In the worst case, it could still reach O(104).

Space Complexity: O(104), for storing distances and the priority queue.

Code Examples (Python):

The provided code examples demonstrate each of these approaches. Remember to adapt the code based on the specific requirements and constraints of your environment. For example, if your environment does not support the deque or heapq, you may need to use standard queue and heap implementations.

Choosing the Right Solution:

  • For simple cases or smaller state spaces, Solution 1 (basic BFS) might be sufficient.
  • For larger state spaces or when the shortest path is far from the starting node, Solution 2 (bidirectional BFS) is significantly more efficient.
  • Solution 3 (A* search) can offer further improvements, especially for complex state spaces where a good heuristic is available. However, it adds complexity in implementation.