Extract edges from adjacent word pairs, then topological sort.
function alienOrder(words): graph = {c: set() for w in words for c in w} inDegree = {c: 0 for c in graph} for i in range(len(words) - 1): w1, w2 = words[i], words[i + 1] if len(w1) > len(w2) and w1.startswith(w2): return "" for c1, c2 in zip(w1, w2): if c1 != c2: if c2 not in graph[c1]: graph[c1].add(c2) inDegree[c2] += 1 break queue = [c for c in inDegree if inDegree[c] == 0] result = [] while queue: c = queue.pop(0) result.append(c) for neighbor in graph[c]: inDegree[neighbor] -= 1 if inDegree[neighbor] == 0: queue.append(neighbor) return "".join(result) if len(result) == len(graph) else ""
time and space.