Problem Link

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        # Find the shortest path: BFS
        if '0000' in deadends:
            return -1
        queue = ['0000']
        deadSet = set(deadends)
        visited = set()
        res = 0
        while queue:
            for _ in range(len(queue)):
                cur = queue.pop(0)
                if cur == target:
                    return res
                for i in range(4):
                    nxt = cur[:i] + str((int(cur[i]) + 1) % 10) + cur[i+1:]
                    if nxt not in deadSet and nxt not in visited:
                        queue.append(nxt)
                        visited.add(nxt)
                    nxt = cur[:i] + str((int(cur[i]) + 9) % 10) + cur[i+1:]
                    if nxt not in deadSet and nxt not in visited:
                        queue.append(nxt)
                        visited.add(nxt)
            res += 1
        return -1