Alien Dictionary

Alien Dictionary hands you a dictionary from an alien language — a list of words already sorted by their alphabet — and asks you to recover that alphabet. It is the classic disguise for a topological sort: the sorted words secretly encode ordering rules between letters.

The slow way first

You might hope to compare every word with every other word and somehow vote on letter positions. But two words only tell you about one ordering — the first place they differ — and comparing all pairs is wasted work: the list is already sorted, so the useful information lives entirely between neighbors. Trying to brute-force a global ordering from scattered clues quickly tangles into contradictions you cannot resolve.

The real question: what single fact does one pair of adjacent words give me? Exactly one ordering edge. Collect those edges and the problem becomes a graph.

The idea: edges from neighbors, then topological sort

Walk through adjacent word pairs. For each pair, scan character by character until they differ. That first differing position tells you that the earlier word's letter comes before the later word's letter — one directed edge u → v. Do this for every neighboring pair and you have a directed graph over the letters. The alien alphabet is any topological sort of that graph: an ordering where every edge points forward.

We use Kahn's algorithm for the sort: repeatedly take a letter with no remaining incoming edges (in-degree 0), output it, and remove its outgoing edges.

Walk through it

Step through the animation. Each adjacent pair lights up the two letters it constrains and draws a directed edge: wrt|wrf gives t → f, wrf|er gives w → e, er|ett gives r → t, and ett|rftt gives e → r. Then the topological sort drains the graph one in-degree-0 letter at a time, filling the answer row: w, then e, then r, then t, then f.

Pseudocode

build a node for every distinct letter
for each pair of ADJACENT words (a, b):
    scan a and b together
    at the first position where they differ:
        add edge a_letter -> b_letter
        stop scanning this pair
topological sort the letter graph (Kahn's algorithm):
    start a queue with every in-degree-0 letter
    repeatedly pop one, append to output, and
    decrement its neighbors; enqueue any that hit 0
return the output letters joined into a string

The Python solution

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                adj[x].add(y); indeg[y] += 1
                break
    q = [c for c in adj if indeg[c] == 0]
    order = []
    while q:
        c = q.pop(0)
        order.append(c)
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return "".join(order)

• adj is the directed graph as a dict of sets; indeg counts incoming edges per letter.
• zip(words, words[1:]) pairs each word with its neighbor — the only pairs that carry information.
• The inner zip(a, b) walks both words together; at the first mismatch we add one edge and break.
• We seed the queue with every in-degree-0 letter, then run Kahn's algorithm: pop, output, and relax neighbors.
• Joining order gives the alphabet. (A full solution would also check for a cycle and the prefix edge case.)

Complexity

With at most 26 distinct letters, V and E are tiny — the work is dominated by scanning the input, so the whole thing is effectively linear in the input size.

When this pattern shows up

Practice