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?

CodePudding user response：

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

possible solution: Try to check whether if that key already exists or not then only start the loop something like this

if c in adjacent:
    for neighbor in adjacent[c]: 
        ......

CodePudding user response：

The function dfs() modifies the visited() dictionary by adding keys.

Specifically, this line:

visited[c] = True

will always add c to the dictionary, since you check whether c is in the visited dictionary immediately above this line.

You could circumvent this issue by inserting every key into the visited dictionary with a value of False, if you know the possible keys in advance. (Unfortunately, the problem is only available if you have LeetCode Premium, so I can't make any suggestions that would pass all of LeetCode's test cases with certainty.)