752. Open the Lock

https://leetcode.com/problems/open-the-lock/

solution

• 最短路径 -> BFS

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int: 
        if '0000' in deadends:
            return -1  # 注意, 如果把deadend和target的判断放在pop后面判断，反而避免杜绝了该问题？
        if target == '0000':
            return 0
        
        deadends = set(deadends)
        visited = set()
        visited.add('0000')
        queue = collections.deque([('0000', 0)])  # 还是要注意这里两层, append时一层
        
        while queue:
            node, step = queue.popleft()     
          
            for i in range(4):
                for j in [1, -1]:
                    new_i = (int(node[i]) + j) % 10
                    new_node = node[:i] + str(new_i) + node[i+1:]

                    if new_node in deadends:
                        continue
                    
                    if new_node == target:
                        return step + 1
                    
                    if new_node not in visited:
                        visited.add(new_node)
                        queue.append((new_node, step + 1))
        return -1

时间复杂度：O(10^4) 空间复杂度：O(10^4)