"RuntimeError: dictionary changed size during iteration"，但是在循环中它没有被改变。

Question

我正在解决这个LeetCode问题，这是我的代码：

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，对吗？

- johan

Answer 1

主要问题在于调用dfs方法时，它使用了这一行代码。

for neighbor in adjacent[c]: 

如果在defaultdict中存在相关值，它将返回该值；如果不存在，则在您尝试访问不存在的键时创建并添加一个键。

可能会触发访问相邻defaultdict的潜在行是

if dfs(neighbor):

邻居可能在相邻的defaultdict中，也可能不在。这会导致defaultdict发生变化。如果它不存在，你可以选择跳过。

- gilf0yle

---

但是那些“c”的键是邻接的（因为有行“for c in adjacent”）。当我调用“dfs（c）”时，字典中应该已经存在这些键。 - johan

你可以做一件事情来代替。对于字典中的x，尝试temp = dict.keys()，然后对于temp中的x...即使字典被修改也可以避免错误。 - gilf0yle

我知道如何让它工作，但我正在寻找为什么会抛出错误的解释。我正在使用来自adjacent本身的键c检查adjacent[c]。这会导致什么错误？ - johan

尝试通过在可能被编辑的位置打印相邻字典来进行调试，最终您将会知道问题所在。 - gilf0yle

好的，我现在找到了罪魁祸首。这是因为在调用 dfs(neighbor) 时，neighbor 可能不在字典中。第一次调用 dfs，dfs(c)，完全没有问题。 - johan

Answer 2

@gilf0yle 指出问题在于 defaultdict 可能会插入新的键。解决方法是在迭代之前将其“冻结”，方法是将其转换为普通的dict。

adjacent = dict(adjacent)  # No more default key insertion from here on
for c in adjacent:
    if dfs(c):
        return ''
return ''.join(reversed(res))

- Addison Klinke