Sponsored
Sponsored
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.
Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.
1from collections import deque
2
3def openLock(deadends, target):
4 deadset = set(deadends)
5 queue = deque([('0000', 0)])
6 visited = set('0000')
7
8 while queue:
9 position, turns = queue.popleft()
10
11 if position == target:
12 return turns
13
14 if position in deadset:
15 continue
16
17 for i in range(4):
18 digit = int(position[i])
19 for move in [-1, 1]:
20 new_digit = (digit + move) % 10
21 new_position = position[:i] + str(new_digit) + position[i+1:]
22
23 if new_position not in visited:
24 visited.add(new_position)
25 queue.append((new_position, turns + 1))
26
27 return -1The 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.
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.
Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.
1function openLock(deadends, target) {
2
The approach is similar to the C++ solution but involves managing two sets, beginSet and endSet, that store states being explored from both directions. The search alternates between these two directions and explores neighbors by rotating each digit of the lock either forward or backward. This minimizes the states processed, especially when the target is near the searched edges.