BFS with deadends in visited set. Generate 8 neighbors per state.
function openLock(deadends, target): dead = set(deadends) if "0000" in dead: return -1 visited = dead.copy() queue = [("0000", 0)] visited.add("0000") while queue: state, steps = queue.pop(0) if state == target: return steps for i in range(4): for d in [-1, 1]: digit = (int(state[i]) + d) % 10 newState = state[:i] + str(digit) + state[i+1:] if newState not in visited: visited.add(newState) queue.append((newState, steps + 1)) return -1
time (bounded state space).