I’m solving this LeetCode problem and here’s my code:
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))
The line for c in adjacent
throws “RuntimeError: dictionary changed size during iteration”, which I don’t understand. I’m not modifying adjacent
in dfs()
, am I?
Advertisement
Answer
The main Problem is when dfs method is called it uses this line
for neighbor in adjacent[c]:
This just returns the associated value if it exists in defaultdict, if it doesn’t exist in it, it creates and adds a key if you try to access key that doesn’t exist.
Potential line that triggers accessing adjacent defaultdict without knowing whether it exist or not is
if dfs(neighbor):
neighbor might be or might not be in adjacent defaultdict this causes defaultdict to change. You might check if it exists if not u might want to skip.