Problem 47 · Graphs

Alien Dictionary

HardClassic DSA & systems

01Problem

Given a list of words sorted in an unknown alphabet's lexicographic order, return a string of the letters in a valid order, or empty string if the ordering is invalid.

02Key insight

Only the first differing character of each adjacent pair yields an edge; then topologically sort. Catch the invalid prefix case ("abc" before "ab") and cycles.

03Solution

solution.pypython25 lines

from collections import deque

def alien_order(words: list[str]) -> str:
    graph: dict[str, set[str]] = {ch: set() for w in words for ch in w}
    indegree = {ch: 0 for ch in graph}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                if y not in graph[x]:
                    graph[x].add(y)
                    indegree[y] += 1
                break
        else:
            if len(a) > len(b):
                return ""  # longer word precedes its own prefix
    queue = deque(ch for ch, d in indegree.items() if d == 0)
    order: list[str] = []
    while queue:
        ch = queue.popleft()
        order.append(ch)
        for nxt in graph[ch]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return "".join(order) if len(order) == len(graph) else ""

Try it first.

TimeO(C) total characters

SpaceO(U^2) for U unique letters

tests.py · 4 passing

tests.pypython4 lines

assert alien_order(["wrt","wrf","er","ett","rftt"]) == "wertf"
assert alien_order(["z","x","z"]) == ""
assert alien_order(["abc","ab"]) == ""
assert sorted(alien_order(["z","z"])) == ["z"]

04Staff-level follow-up

How to tell if the order is unique? It is unique iff Kahn's queue never holds more than one node at a time.