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 <= 500deadends[i].length == 4target.length == 4deadends.target and deadends[i] consist of digits only.The problem can be visualized as a graph traversal task, where each state of the lock is a node, and valid moves between states are edges. We use Breadth-First Search (BFS) to explore all possibilities level by level, which ensures that the first time we reach the target state, we have used the minimum number of steps possible.
To implement this approach, initialize a queue for BFS starting with the initial state '0000' and count as 0. Use a set to store deadends and another set for visited states to prevent reprocessing. For each current state, if it is the target, return the count. Otherwise, generate all possible next states by turning each wheel forward and backward, and enqueue all of them that aren't in deadends or the visited set.
The code implements a BFS approach using a queue where each element is a tuple containing the current state and the number of moves taken to reach it. The deadends and visited states are stored in sets to allow quick lookup operations. We iterate through each wheel of the lock, creating new states by incrementing or decrementing the current digit, making sure to wrap around from 9 to 0 or 0 to 9. If a state hasn't been visited or isn't a deadend, it's added to the queue of states to explore next.
Java
Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.
To further optimize the BFS approach, a Bidirectional BFS can be employed. We initiate two BFS processes, one from the initial state '0000' and the other from the target state. If they meet at any node, the combined path length gives the answer. This approach can significantly reduce the number of states explored as two searches from opposite ends tend to cover less ground.
The bidirectional BFS starts two searches: one from the initial state '0000' and the other from the target. During each iteration, we always expand the smaller frontier. If they meet, the shortest path is found. By swapping between the starting and ending search direction, we prevent excessive growth of either search frontier. Overall, this reduces the breadth of the search space.
JavaScript
Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states. |
| Bidirectional Breadth-First Search | Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets. |
Open the Lock - Leetcode 752 - Python • NeetCode • 45,169 views views
Watch 9 more video solutions →Practice Open the Lock with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor