The machine receives words sorted in an unknown alien alphabet and must deduce the letter order. Adjacent words give partial information: at the first differing character between two adjacent words, the earlier character precedes the later one.
The key insight is that each such comparison produces one directed edge in a letter graph, and the order is a topological sort of that graph. The machine must also detect contradictions — a cycle means no valid alphabet exists and the answer is empty.
The approach has three steps. First, compare each adjacent word pair, stop at the first differing character, and add an edge from the earlier letter to the later one, collecting every distinct letter as a node. Second, run Kahn's algorithm: start with zero-in-degree letters, pop them into the answer, and decrement dependents' in-degrees. Third, if the answer omits any letter, a cycle exists and the machine returns empty. Time is O(total characters) and space is O(V + E).
The trickiest edge case is the prefix trap: 'ab' before 'abc' is fine, but the reverse ('abc' before 'ab') is a contradiction and must yield empty. Letters appearing in only one word still need nodes and must appear in the output.
from collections import defaultdict, deque
def alienOrder(words):
adj = defaultdict(set)
indegree = {c: 0 for word in words for c in word}
for w1, w2 in zip(words, words[1:]):
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in adj[c1]:
adj[c1].add(c2)
indegree[c2] += 1
break
else:
if len(w1) > len(w2):
return ""
q = deque(c for c in indegree if indegree[c] == 0)
order = []
while q:
c = q.popleft()
order.append(c)
for nxt in adj[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return "".join(order) if len(order) == len(indegree) else ""