LC752. Open the Lock

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if "0000" in deadends: return -1
 
        def children(password):
            res = []
            for i in range(4):
                digit = (int(password[i]) + 1) % 10
                res.append(password[:i] + str(digit) + password[i + 1:])
                digit = (int(password[i]) - 1 + 10) % 10
                res.append(password[:i] + str(digit) + password[i + 1:])
            return res
        
        q = deque([("0000", 0)])
        visited = set(deadends)
 
        while q:
            password, turns = q.popleft()
 
            if password == target:
                return turns
            
            for child in children(password):
                if child in visited:
                    continue
                
                visited.add(child)
                q.append((child, turns + 1))
        
        return -1

Complexity

Time: $O(10^4)\sim O(1)$
Space: $O(10^4)\sim O(1)$