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.
1import java.util.*;
2
3class Solution {
4 public int openLock(String[] deadends, String target) {
5 Set<String> deadset = new HashSet<>(Arrays.asList(deadends));
6 Queue<String> queue = new LinkedList<>();
7 Set<String> visited = new HashSet<>();
8 queue.offer("0000");
9 visited.add("0000");
10 int turns = 0;
11
12 while (!queue.isEmpty()) {
13 int size = queue.size();
14 for (int i = 0; i < size; i++) {
15 String position = queue.poll();
16 if (position.equals(target)) return turns;
17 if (deadset.contains(position)) continue;
18 for (int j = 0; j < 4; j++) {
19 char[] chars = position.toCharArray();
20 char orig = chars[j];
21 chars[j] = (char)((orig - '0' + 1) % 10 + '0');
22 String next = new String(chars);
23 if (!visited.contains(next)) {
24 queue.offer(next);
25 visited.add(next);
26 }
27 chars[j] = orig;
28 chars[j] = (char)((orig - '0' + 9) % 10 + '0');
29 next = new String(chars);
30 if (!visited.contains(next)) {
31 queue.offer(next);
32 visited.add(next);
33 }
34 }
35 }
36 turns++;
37 }
38 return -1;
39 }
40}The Java solution closely follows the BFS from the Python code. A queue stores states to explore, and we maintain a visited set to track states we've already processed. For each state, explore its neighbors by rotating each wheel one step forward and backward, checking to skip deadends and revisited states. The depth of the BFS tree is returned when the target state is reached.
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.
1#include <iostream>
2#include <unordered_set>
3#include <queue>
4#include <string>
5#include <vector>
using namespace std;
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
unordered_set<string> beginSet, endSet, visited;
beginSet.insert("0000");
endSet.insert(target);
int level = 0;
while (!beginSet.empty() && !endSet.empty()) {
if (beginSet.size() > endSet.size()) {
swap(beginSet, endSet);
}
unordered_set<string> temp;
for (auto pos : beginSet) {
if (endSet.find(pos) != endSet.end()) return level;
visited.insert(pos);
for (int i = 0; i < 4; ++i) {
string newPos = pos;
char orig = pos[i];
for (int j = -1; j <= 1; j += 2) {
newPos[i] = (orig - '0' + j + 10) % 10 + '0';
if (!visited.count(newPos) && !dead.count(newPos)) {
temp.insert(newPos);
}
}
}
}
++level;
swap(beginSet, temp);
}
return -1;
}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.