• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

752. Open the Lock

2周前 (04-07) 6次浏览

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 can't reach the target without getting stuck.
```

Example 4:

```Input: deadends = ["0000"], target = "8888"
Output: -1```
``` 1 class Solution {
2     public int openLock(String[] deadends, String target) {
3         Queue<String> q = new LinkedList<>();
4         Set<String> visited = new HashSet<>(Arrays.asList(deadends));
5         if (visited.contains("0000")) return -1;
6         q.offer("0000");
8         int level = 0;
9         while(!q.isEmpty()) {
10             int size = q.size();
11             for (int j = 1; j <= size; j++) {
12                 String s = q.poll();
13                 if(s.equals(target)) return level;
14                 StringBuilder sb = new StringBuilder(s);
15                 for(int i = 0; i < 4; i ++) {
16                     char c = sb.charAt(i);
17                     String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1);
18                     String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1);
19                     if(!visited.contains(s1)) {
20                         q.offer(s1);
22                     }
23                     if(!visited.contains(s2)) {
24                         q.offer(s2);