Graph Exploration Target: 15s
Build ordering graph from adjacent word pairs. Topological sort gives valid alphabet. Detect cycles for invalid input.
def alienOrder(words):
graph = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1[:len(w2)] == w2:
return "" # invalid: prefix comes after
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topo sort
color = {} # 1=gray, 2=black
order = []
def dfs(c):
if c in color: return color[c] == 2
color[c] = 1
for nb in graph[c]:
if not dfs(nb): return False
color[c] = 2
order.append(c)
return True
return ''.join(reversed(order)) if all(dfs(c) for c in graph) else ''Type it from memory. Go.