This is the 25th day of my participation in Gwen Challenge
Topic describes
This is 752 on LeetCode. Opening the turntable lock is medium difficulty.
Tag: “bidirectional BFS”, “heuristic search”, “AStar algorithm”, “IDAStar algorithm”
You have a turntable lock with four round paddles. Each dial wheel has 10 Numbers: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each dial wheel can rotate freely: for example, ‘9’ becomes ‘0’ and ‘0’ becomes ‘9’. Each rotation can only rotate one digit of one dial wheel.
The initial lock number is ‘0000’, a string representing the numbers of the four dial wheels.
The list deadends contains a set of death numbers. Once the number of the dial wheel matches any element in the list, the lock is permanently locked and cannot be rotated.
The string target represents the number that can be unlocked. You need to give the minimum number of rotations required to unlock it. If you can’t unlock it anyway, return -1.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Could move the sequence of "0000" - > "1000" - > "1100" - > "1200" - > "1201" - > "1202" - > "0202". Note that sequences such as "0000" -> "0001" -> "0002" -> "0102" -> "0202" cannot be unlocked because the lock will be locked when "0102" is tapped.Copy the codeExample 2:
Deadends = ["8888"], target = "0009" Output: 1Copy the codeExample 3:
Input: Deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Description: Cannot rotate to target number and is not locked.Copy the codeExample 4:
Input: deadends = ["0000"], target = "8888Copy the codeTip:
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- Target is not in deadends
- Target and deadends[I] consist of only a few digits
Fundamental analysis
First of all, I suggest you do “127. Solitar” first, and then come back to this question as an “exercise”.
127. It is difficult to locate the word solitaire. Mainly reflected in the scope of data, thinking difficulty “127. Word solitaire” is not more difficult than this topic, bold to do.
The link to the original question “127. The word Solitaire” is here and the solution to the related question is here.
Back to the question, according to the passage, it can be determined that this is a “shortest” problem.
This kind of problem is usually solved by “BFS”, but naive BFS usually leads to the search space explosion problem.
So we can use the same idea as (题 干)127.
Two-way BFS
We know that the recursion tree is a multi-order tree.
When solving with naive BFS, there will be at most “two layers” of search nodes in the queue.
Therefore, the upper bound of the search space depends on the width corresponding to the depth of the search level where the target node is located.
The figure below shows the potential search space explosion problem for naive BFS:
In a naive BFS implementation, the bottleneck of space depends primarily on the maximum width in the search space.
So is there a way to avoid using such a wide search space and still get the desired results?
Two-way BFS can solve this problem:
Start the search in both directions at the same time. Once you find the same value, you have found a shortest path that connects the start and end points.
In the case of “solution”, “certain data range” and “the number of hierarchical nodes increases by multiples or exponentials”, the search space of “bidirectional BFS” is usually only one hundredth or even one thousandth of the space consumption of “naive BFS”.
The basic implementation idea of “bidirectional BFS” is as follows:
- Create “two queues” for search in two directions;
- Create “two hash tables” to “resolve repeated searches for the same node” and “record conversion times”;
- To make the two search directions as “average” as possible, each time the value is expanded from the queue, determine which queue has a smaller capacity first.
- If the node searched by the other party is found during the search, the shortest path is found.
The pseudo-code corresponding to the basic idea of “bidirectional BFS” is roughly as follows:
D1 and d2 are two-direction queues. M1 and m2 are two-direction hash tables, which record the distance between each node and the starting point// If both queues are not empty, it is necessary to continue searching
// If one of the queues is empty, the destination node in that direction cannot be found
while(! d1.isEmpty() && ! d2.isEmpty()) {if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else{ update(d2, m2, m1); }}// update logic for fetching an element from queue D for "one full extension"
void update(Deque d, Map cur, Map other) {}
Copy the codeBack to our problem, let’s see how we can use “bidirectional BFS” to solve it.
This is probably the first time for many of you to encounter “bidirectional BFS”, so I wrote a lot of comments this time.
It is recommended that you read with a basic understanding of “bidirectional BFS”.
Code:
class Solution {
String t, s;
Set<String> set = new HashSet<>();
public int openLock(String[] _ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : _ds) set.add(d);
if (set.contains(s)) return -1;
int ans = bfs();
return ans;
}
int bfs(a) {
// d1 means start search from s (forward)
// d2 means search from end t (reverse)
Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
* E.G.S * m1 = {"1000":1} stands for "1000". * m2 = {"9999":3} stands for "1000" "9999" is produced by replacing t="9996" three times with */
Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
d1.addLast(s);
m1.put(s, 0);
d2.addLast(t);
m2.put(t, 0);
/* * If both queues are not empty, it is necessary to search down * * If one of the queues is empty, the destination node in that direction cannot be searched * * for example, if d1 is empty, the destination node in that direction cannot be searched from s to t, and there is no need to search backwards */
while(! d1.isEmpty() && ! d2.isEmpty()) {int t = -1;
if (d1.size() <= d2.size()) {
t = update(d1, m1, m2);
} else {
t = update(d2, m2, m1);
}
if(t ! = -1) return t;
}
return -1;
}
int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
String poll = deque.pollFirst();
char[] pcs = poll.toCharArray();
int step = cur.get(poll);
// Enumerates which character to replace
for (int i = 0; i < 4; i++) {
// Enumerate the offset [-1,1] directly and skip 0
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
// Find the replacement string STR
int origin = pcs[i] - '0';
int next = (origin + j) % 10;
if (next == -1) next = 9;
char[] clone = pcs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
if (cur.containsKey(str)) continue;
// If it is found in the "other direction", the shortest path is found, otherwise join queue
if (other.containsKey(str)) {
return step + 1 + other.get(str);
} else {
deque.addLast(str);
cur.put(str, step + 1); }}}return -1; }}Copy the codeAStar algorithm
A heuristic function of A* can be designed directly according to the rules in this case.
For example, for two states A and B, the “theoretical minimum conversion times” can be calculated directly: the sum of conversion costs for different characters.
Note: since we measure a characterstrThe valuation is based on the target stringtargetIs the benchmark, so we can only make suretargetThe “shortest distance” when leaving the team cannot ensure the “shortest distance” when the middle node leaves the team. Therefore, we cannot decide whether to join the team simply based on whether a node has been in the team, but also based on whether the “minimum distance” of the current node has been updated.
This is critical and is reflected at the code level in the judgment of map.get(STR).step > poll.step + 1.
Note: This case is overdone with A*, but usually we need to “make sure there is A solution” before A* heuristic search is of real value. Unless t itself is in deadends, we cannot judge in advance whether there is a solution or not. A* is not as good as “bidirectional BFS” for no solution.
Code:
class Solution {
class Node {
String str;
int val, step;
/** * STR: corresponding string * val: estimate (minimum conversion cost to target string) * step: how many steps to convert the corresponding string */
Node(String _str, int _val, int_step) { str = _str; val = _val; step = _step; }}int f(String str) {
int ans = 0;
for (int i = 0; i < 4; i++) {
int cur = str.charAt(i) - '0', target = t.charAt(i) - '0';
int a = Math.min(cur, target), b = Math.max(cur, target);
// Set min between forward turn and reverse turn
int min = Math.min(b - a, a + 10 - b);
ans += min;
}
return ans;
}
String s, t;
Set<String> set = new HashSet<>();
public int openLock(String[] ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : ds) set.add(d);
if (set.contains(s)) return -1;
PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
Map<String, Node> map = new HashMap<>();
Node root = new Node(s, f(s), 0);
q.add(root);
map.put(s, root);
while(! q.isEmpty()) { Node poll = q.poll();char[] pcs = poll.str.toCharArray();
int step = poll.step;
if (poll.str.equals(t)) return step;
for (int i = 0; i < 4; i++) {
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
int cur = pcs[i] - '0';
int next = (cur + j) % 10;
if (next == -1) next = 9;
char[] clone = pcs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
// If STR has not been searched, or STR's "minimum distance" is updated, STR is in the queue
if(! map.containsKey(str) || map.get(str).step > step +1) {
Node node = new Node(str, step + 1 + f(str), step + 1); map.put(str, node); q.add(node); }}}}return -1; }}Copy the codeIDA * algorithm
Also we can use the DFS based heuristic IDA* algorithm:
- Still use
f()As a function of valuation - Finite number of rotations: the total number of rotations does not exceed a certain threshold Max \maxmax.
- Use the idea of “iterative deepening” to find the shortest distance
Ideally, due to forward and reverse rotations, each wheel will consume no more than 555 times from any number to any number, so Max =5∗4\ Max =5 * 4max=5∗4 is ideally set.
However, considering the existence of deadends, we need to define Max \maxmax more conservatively: Max =10∗4\ Max =10 * 4max=10∗4.
But such a threshold setting, combined with the IDA* algorithm repeatedly traversing all nodes “less than the distance from the target node” each time, carries a significant TLE risk.
So we need to use dynamic thresholds: instead of using fixed thresholds, we usetargetCalculate the “maximum transfer cost” as our “deepest order of magnitude”.
PS. The above threshold analysis is a scientific practice. For this problem, use Max =5∗4\ Max =5 * 4max=5∗4 directly, and the effect is good.
However, it must be noted that Max =5∗4\ Max =5 * 4max=5∗4 May be a wrong threshold. In this case, the starting point is 0000. Consider putting all forward transformed states into deadends with target 2222. At this point we can only specify that the path from 0000 to 9999 and back to 2222 is not in deadends.
Max =5∗4\ Max =5 * 4max=5∗4 Don’t try. I submitted it to 🤣
Code:
class Solution {
String s, t;
String cur;
Set<String> set = new HashSet<>();
Map<String, Integer> map = new HashMap<>();
public int openLock(String[] ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : ds) set.add(d);
if (set.contains(s)) return -1;
int depth = 0, max = getMax();
cur = s;
map.put(cur, 0);
while(depth <= max && ! dfs(0, depth)) {
map.clear();
cur = s;
map.put(cur, 0);
depth++;
}
return depth > max ? -1 : depth;
}
int getMax(a) {
int ans = 0;
for (int i = 0; i < 4; i++) {
int origin = s.charAt(i) - '0', next = t.charAt(i) - '0';
int a = Math.min(origin, next), b = Math.max(origin, next);
int max = Math.max(b - a, a + 10 - b);
ans += max;
}
return ans;
}
int f(a) {
int ans = 0;
for (int i = 0; i < 4; i++) {
int origin = cur.charAt(i) - '0', next = t.charAt(i) - '0';
int a = Math.min(origin, next), b = Math.max(origin, next);
int min = Math.min(b - a, a + 10 - b);
ans += min;
}
return ans;
}
boolean dfs(int u, int max) {
if (u + f() > max) return false;
if (f() == 0) return true;
String backup = cur;
char[] cs = cur.toCharArray();
for (int i = 0; i < 4; i++) {
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
int origin = cs[i] - '0';
int next = (origin + j) % 10;
if (next == -1) next = 9;
char[] clone = cs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
if(! map.containsKey(str) || map.get(str) > u +1) {
cur = str;
map.put(str, u + 1);
if (dfs(u + 1, max)) return true; cur = backup; }}}return false; }}Copy the codeThe last
This is the No.751 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.