$ cat ./coding/752-open-the-lock.md

────────────────────────────────────────────────────────────

752. Open the Lock

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:        

        visited = set()
        for deadend in deadends:
            visited.add(deadend)

        root = '0000'

        steps = 0
        queue = deque([root])
        visited.add(root)
        while queue:
            for i in range(len(queue)):
                node = queue.popleft()
                if node in deadends:
                    continue
                if node == target:
                    return steps
                for i in range(4):
                    plus_one = '0' if node[i] == '9' else str(int(node[i]) + 1)
                    child = node[:i] + plus_one + node[i+1:]
                    if child not in visited:
                        queue.append(child)
                        visited.add(child)
                    minus_one = '9' if node[i] == '0' else str(int(node[i]) - 1)
                    child = node[:i] + minus_one + node[i+1:]
                    if child not in visited:
                        queue.append(child)
                        visited.add(child)
            steps += 1

        return -1

class Solution:

    def generate_keys(self, node):
        keys = []
        for i in range(4):
            plus_one = '0' if node[i] == '9' else str(int(node[i]) + 1)
            minus_one = '9' if node[i] == '0' else str(int(node[i]) - 1)
            keys.append(node[:i] + plus_one + node[i+1:])
            keys.append(node[:i] + minus_one + node[i+1:])
        return keys

    def openLock(self, deadends: List[str], target: str) -> int:         
        visited = set()
        for deadend in deadends:
            visited.add(deadend)

        root = '0000'
        steps = 0
        queue = deque([root])
        visited.add(root)
        while queue:
            for i in range(len(queue)):
                node = queue.popleft()
                if node in deadends:
                    continue
                if node == target:
                    return steps
                for key in self.generate_keys(node):
                    if key not in visited:
                        queue.append(key)
                        visited.add(key)
            steps += 1

        return -1

$ ls ./coding/ | grep -v 752-open-the-lock