python - 力扣 752 : Open the Lock TLE with BFS

Question

我正在尝试解决leetcode问题https://leetcode.com/problems/open-the-lock/与 BFS 并提出了下面的方法。

def openLock(self, deadends: List[str], target: str): -> int
      def getNeighbors(node) ->List[str]:
            neighbors = []
            dirs = [-1, 1]
            for i in range(len(node)):
                for direction in dirs:
                    x = (int(node[i]) + direction) % 10
                    neighbors.append(node[:i] + str(x) + node[i+1:])
            return neighbors
                        
        start = '0000'
        if start in deadends:
            return -1
        queue = deque()
        queue.append((start, 0))
        turns = 0
        visited = set()
        deadends = set(deadends)
        while queue:
            state, turns = queue.popleft()
            visited.add(state)
            if state == target:
                return turns
            for nb in getNeighbors(state):
                if nb not in visited and nb not in deadends:   
                    queue.append((nb, turns+1))
        return -1

但是此代码遇到了超出时间限制的异常，并且仅通过了 2/48 的测试用例。对于前。测试用例的死端为 ["8887","8889","8878","8898","8788","8988","7888","9888"] 和目标是“8888”(开头始终是“0000”)我的解决方案TLE。我注意到，如果我本质上更改一行并将相邻节点添加到我的内部循环中的访问集中，我的解决方案将通过该测试用例和所有其他测试用例。

for nb in getNeighbors(state):
     if nb not in visited and nb not in deadends:   
         visited.add(nb)
         queue.append((nb, turns+1))

我的 while 循环就变成了

while queue:
            state, turns = queue.popleft()
            if state == target:
                return turns
            for nb in getNeighbors(state):
                if nb not in visited and nb not in deadends:   
                    visited.add(nb)
                    queue.append((nb, turns+1))

有人可以解释为什么第一种方法会遇到 TLE 而第二种方法不会？

Answer 1

是的。绝对地。您需要在项目第一次添加到队列时将其添加到 visited 中，而不是在它从队列中删除时。否则你的队列将会呈指数级增长。

让我们看看 1111。您的代码会将 1000、0100、0010、0001(和其他)添加到队列中。然后，您的代码将添加 1100、1010、1001、0110、0101、0011 等两次，因为它们是队列中两个元素的邻居，并且尚未被访问过。然后将 1110、1101、1011、0111 各相加四次。如果您正在搜索 5555，您的队列中将会有很多重复项。

将 visited 变量的名称更改为 seen。请注意，一旦将某个项目放入队列中，就无需再次将其放入队列中。

说真的，尝试无死角地搜索 5555。当您找到它时，查看队列并查看队列中有多少元素，以及队列中有多少不同元素。