# 752 Open the Lock

## 752. [Open the Lock](https://leetcode.com/problems/open-the-lock/description/)

## 1. Question

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
```

**Note:**

1. The length of`deadends`will be in the range`[1, 500]`.
2. `target`will not be in the list`deadends`.
3. Every string in`deadends`and the string`target`will be a string of 4 digits from the 10,000 possibilities`'0000'`

   to`'9999'`.

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add("0000");
        visited.add("0000");

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curCode = queue.remove();

                if (deads.contains(curCode)) {
                    continue;
                }
                else if (curCode.equals(target)) {
                    return level;
                }
                else {
                    StringBuilder sb = new StringBuilder(curCode);
                    for (int j = 0; j < 4; j++) {
                        char c = sb.charAt(j);

                        String nextCode1 = sb.substring(0, j) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(j + 1);
                        String nextCode2 = sb.substring(0, j) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(j + 1);

                        if (!visited.contains(nextCode1) && !deads.contains(nextCode1)) {
                            visited.add(nextCode1);
                            queue.add(nextCode1);
                        }

                        if (!visited.contains(nextCode2) && !deads.contains(nextCode2)) {
                            visited.add(nextCode2);
                            queue.add(nextCode2);
                        }
                    }
                }
            }
            ++level;
        }
        return -1;
    }
}
```

**(2) Bi-directional BFS**

```java
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        Set<String> begin = new HashSet<>();
        Set<String> end = new HashSet<>();

        begin.add("0000");
        end.add(target);

        int level = 0;

        while (!begin.isEmpty() && !end.isEmpty()) {
            // Always start with a smaller set
            if (begin.size() > end.size()) {
                Set<String> set = begin;
                begin = end;
                end = set;
            }
            Set<String> temp = new HashSet<>();
            for (String code : begin) {
                if (deads.contains(code)) {
                    continue;
                }


                for (int i = 0; i < code.length(); i++) {
                    char c = code.charAt(i);
                    String nextCode1 = code.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + code.substring(i + 1);
                    String nextCode2 = code.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + code.substring(i + 1);

                    if (end.contains(nextCode1) || end.contains(nextCode2)) {
                        return level + 1;
                    }

                    if (!deads.contains(nextCode1)) {
                        temp.add(nextCode1);
                    }

                    if (!deads.contains(nextCode2)) {
                        temp.add(nextCode2);
                    }
                }
            }
            ++level;
            begin = temp;
        }
        return -1;
    }
}
```

## 3. Time & Space Complexity

**BFS**: 时间复杂度O(m ^ n + d), m是在转轮上digit的个数(10 in this case), n是lock的digit个数(4 in this case)， d是deadends的size， 空间复杂度O(m ^ n + d)

**Bi-directional BFS:** 时间复杂度O(m ^ n + d), m是在转轮上digit的个数(10 in this case), n是lock的digit个数(4 in this case)， d是deadends的size， 空间复杂度O(m ^ n + d)