Open the Lock

Solution

Layered BFS

from collections import deque

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        start = '0000'
        dd = set(deadends)
        if start in dd:
            return -1
        frontiers = deque()
        frontiers.append(start)
        visited = set()
        visited.add(start)
        res = 0
        
        while frontiers:
            curr_level_nodes_count = len(frontiers)
            for _ in range(curr_level_nodes_count):
                curr = frontiers.popleft()
                if curr == target:
                    return res
                # get neighbors
                neighbors = []
                for i in range(len(curr)):
                    for delta in [-1, 1]:
                        next = curr[:i] + str((int(curr[i]) + delta) % 10) + curr[i+1:]
                        if (next not in visited) and (next not in dd):
                            frontiers.append(next)
                            visited.add(next)
            res += 1
        return -1