1
class Solution:
2
    def openLock(self, deadends: List[str], target: str) -> int:
3
        def neighbor(s):
4
            res = []
5
            for i, c in enumerate(s):
6
                res.append(
7
                    s[:i] + chr((ord(c) - ord("0") + 9) % 10 + ord("0")) + s[i + 1 :]
8
                )
9
                res.append(
10
                    s[:i] + chr((ord(c) - ord("0") + 1) % 10 + ord("0")) + s[i + 1 :]
11
                )
12
            return res
13

14
        deadends = set(deadends)
15
        if "0000" in deadends:
16
            return -1
17
        ans = 0
18
        queue = deque(["0000"])
19
        vis = set()
20
        while queue:
21
            l = len(queue)
22
            for _ in range(l):
23
                cur = queue.popleft()
24
                if cur == target:
25
                    return ans
26
                for nxt in neighbor(cur):
27
                    if nxt not in vis and nxt not in deadends:
28
                        queue.append(nxt)
29
                        vis.add(nxt)
30
            ans += 1
31
        return -1