Topological Sort - Alien Dictionary (Infer Character Order)
Consider the following buggy code snippet for the alien dictionary problem. Which line contains the subtle bug that can cause incorrect results on inputs where a word is a prefix of the next word?
from collections import defaultdict, deque
def alienOrder(words):
graph = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
# BUG: Missing prefix invalid case check here
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in graph[w1[j]]:
graph[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
queue = deque([c for c in in_degree if in_degree[c] == 0])
order = []
while queue:
c = queue.popleft()
order.append(c)
for nei in graph[c]:
in_degree[nei] -= 1
if in_degree[nei] == 0:
queue.append(nei)
if len(order) < len(in_degree):
return ""
return "".join(order)
