-
Notifications
You must be signed in to change notification settings - Fork 2
/
OpenTheLock.java
64 lines (56 loc) · 1.42 KB
/
OpenTheLock.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.algorithm.playground.leetcode.problems.lc700.lc752;
import java.util.*;
/**
* https://leetcode.com/problems/open-the-lock/description/
*/
public class OpenTheLock {
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deadendsSet = new HashSet<>(Arrays.asList(deadends));
Set<String> visited = new HashSet<>();
Queue<String> queue = new ArrayDeque<>();
queue.add("0000");
visited.add("0000");
int step = -1;
boolean found = false;
while (!queue.isEmpty() && !found) {
step++;
int size = queue.size();
while (size > 0) {
String s = queue.poll();
size--;
//noinspection ConstantConditions
if (s.equals(target)) {
found = true;
break;
}
if (deadendsSet.contains(s)) {
continue;
}
StringBuilder builder = new StringBuilder(s);
for (int i = 0; i < builder.length(); i++) {
char ch = builder.charAt(i);
builder.setCharAt(i, next(ch));
String next = builder.toString();
if (visited.add(next)) {
queue.add(next);
}
builder.setCharAt(i, prev(ch));
next = builder.toString();
if (visited.add(next)) {
queue.add(next);
}
builder.setCharAt(i, ch);
}
}
}
return found ? step : -1;
}
private char next(char ch) {
return ++ch > '9' ? '0' : ch;
}
private char prev(char ch) {
return --ch < '0' ? '9' : ch;
}
}
}