# 752. Open the Lock

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

``````class Solution {
public:
int openLock(vector<string>& deadends, string target) {
int res = 0;
unordered_set<string> visited{{"0000"}};
queue<string> q{{"0000"}};
while (!q.empty()) {
++res;
for (int k = q.size(); k > 0; --k) {
auto t = q.front(); q.pop();
for (int i = 0; i < t.size(); ++i) {
for (int j = -1; j <= 1; ++j) {
if (j == 0) continue;
string str = t;
str[i] = ((t[i] - '0') + 10 + j) % 10 + '0';
if (str == target) return res;
visited.insert(str);
}
}
}
}
return -1;
}
};
``````

``````class Solution {
public:
int openLock(vector<string>& deadends, string target) {
int res = 0;
unordered_set<string> visited{{"0000"}};
queue<string> q{{"0000"}};
while (!q.empty()) {
++res;
for (int k = q.size(); k > 0; --k) {
auto t = q.front(); q.pop();
for (int i = 0; i < t.size(); ++i) {
char c = t[i];
string str1 = t.substr(0, i) + to_string(c == '9' ? 0 : c - '0' + 1) + t.substr(i + 1);
string str2 = t.substr(0, i) + to_string(c == '0' ? 9 : c - '0' - 1) + t.substr(i + 1);
if (str1 == target || str2 == target) return res;
visited.insert(str1);
visited.insert(str2);
}
}
}
return -1;
}
};
``````

https://leetcode.com/problems/open-the-lock

https://leetcode.com/problems/open-the-lock/discuss/110230/BFS-solution-C++

https://leetcode.com/problems/open-the-lock/discuss/110237/Regular-java-BFS-solution-and-2-end-BFS-solution-with-improvement

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation