python - "RuntimeError: dictionary changed size during iteration"但在循环中没有改变

Question

我正在解决 this LeetCode problem这是我的代码:

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adjacent = defaultdict(set)
        
        for i in range(1, len(words)):
            w1, w2 = words[i - 1], words[i]
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    adjacent[w1[j]].add(w2[j])  # modify, not in the loop causing error
                    break
        
        visited = dict()
        res = []
        
        def dfs(c):
            if c in visited:
                return visited[c]
            
            visited[c] = True
            for neighbor in adjacent[c]:  # read only
                if dfs(neighbor):
                    return True
            visited[c] = False
            res.append(c)
            return False
        
        for c in adjacent:  # RuntimeError: dictionary changed size during iteration
            if dfs(c):
                return ''
        return ''.join(reversed(res))

for c in adjacent 行抛出“RuntimeError: dictionary changed size during iteration”，我不明白。我不是在修改 dfs() 中的 adjacent 吗？

Answer 1

主要问题是调用 dfs 方法时使用了这一行

for neighbor in adjacent[c]: 

如果关联值存在于 defaultdict 中，它只返回关联值，如果它不存在，它会在您尝试访问不存在的 key 时创建并添加一个 key 。

在不知道是否存在的情况下触发访问相邻defaultdict的潜在行是

if dfs(neighbor):

邻居可能在也可能不在相邻的 defaultdict 中，这会导致 defaultdict 发生变化。你可能会检查它是否存在，如果不存在你可能想跳过。