← DSA Atlas
Dedicated problem page · #269

Alien Dictionary

HardTopological SortDerive edges from adjacent-item comparisons, then topologically sortTopological sort over a character graph (Kahn's BFS)
Solve on LeetCode ↗
269
HardTopological SortTopological sort over a character graph (Kahn's BFS)Derive edges from adjacent-item comparisons, then topologically sort

Alien Dictionary

Given a list of words sorted lexicographically by the rules of an unknown alien language, return a string of the language's letters in a valid order. The first place two adjacent words differ reveals that the earlier word's character precedes the later word's character. Return any valid order, or "" if the ordering is contradictory or invalid.

Open official problem prompt ↗
In plain English

Recover a consistent global ordering of the alphabet from local sorted-order evidence between neighboring words.

Picture it like this

Like reconstructing a tournament ranking from a list of match results: each 'A beat B' is one edge, and you want a standings list consistent with every result.

Example
Input
words = ["wrt", "wrf", "er", "ett", "rftt"]
Output
"wertf"
Why
Adjacent comparisons give t<f, w<e, r<t, e<r, which linearize to w, e, r, t, f.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of only lowercase English letters
Pattern lesson

See the pattern, then code

Derive edges from adjacent-item comparisons, then topologically sort
Recognition clue

You are handed sorted data and asked to recover the ordering rule; each adjacent pair yields one precedence edge, turning it into a topological sort problem.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. Only the first differing character between two neighboring words carries information; that single pair gives one directed edge, and the whole alphabet's order is the topological sort of those edges.

New words, made simpleKnow these before the algorithm
First differing character
The earliest index where two adjacent words disagree; the only place a comparison yields an ordering fact.
Invalid prefix
A word that is a prefix of the one before it (e.g. 'abc' then 'ab'), which violates lexicographic sorting.
Isolated letter
A character that appears but is in no comparison; it must still be included in the output.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Compare all character positions

Wrong: only the first difference is informative; later positions can inject false edges.

Add edges for every position where two words differ.

Time O(C)Space O(U + E)
Best choiceFirst-difference edges + topological sort

Correct and linear; handles cycles and isolated letters cleanly.

One edge per adjacent pair plus a prefix-validity check, then Kahn's sort over the letters.

Time O(C)Space O(U + E)
The rule we keep true

Invariant

The graph contains exactly the precedence facts implied by adjacent words, no more; every emitted letter has all its predecessors already emitted.

Why this is correct

Reasoning

Lexicographic sorting guarantees the first differing character between neighbors is the sole ordering constraint. Collecting these into a DAG and topologically sorting yields an order consistent with all evidence; a cycle (contradiction) or an unresolved prefix violation makes a valid order impossible, signaled by "".

The algorithm in three movesSay these aloud before coding
1Initialize every distinct character with in-degree 0 so isolated letters still appear

edges: t->f, w->e, r->t, e->r

2For each adjacent word pair, scan to the first differing character and add edge first_char -> second_char (once)

indeg: w0 e1 r1 t1 f1

3Detect the invalid prefix case: a longer word appearing before its own prefix means no valid order

order = w,e,r,t,f -> "wertf"

4Run Kahn's topological sort; if it emits every character return the string, else return "" for a cycle

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
w0
r1
t2
f3
e4
1 · Readall words
2 · AskWhich letters exist?
3 · Update stateindeg keys = {w, r, t, f, e}
4 · ResultFive letters tracked.
Key takeaway

The four precedence edges chain the five letters into the order w, e, r, t, f.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-5Seed every letter

    Using a dict keyed by all characters ensures isolated letters are still output.

  2. 2
    Lines 6-14Extract one edge per pair

    Break at the first difference; the for/else catches the invalid-prefix case when no difference is found.

  3. 3
    Lines 15-24Topological sort the letters

    Standard Kahn's peeling over the character graph.

  4. 4
    Lines 25Cycle guard

    If not every letter was emitted, the evidence was contradictory, so return "".

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single word -> return its unique letters in any order
  • ['abc', 'ab'] -> invalid prefix, return ""
  • A letter that never participates in a difference must still appear
  • Contradictory evidence forming a cycle -> return ""
!

Common beginner mistakes

  • Adding edges for every differing position instead of only the first
  • Forgetting the prefix check so 'abc' before 'ab' is wrongly accepted
  • Dropping isolated letters by building the letter set only from edges
  • Adding a duplicate edge and double-counting in-degree, which can leave a valid node stuck
Check your understanding

Why must the edge come only from the first differing character and not from every mismatch?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)#2050Parallel Courses IIITopological longest path (critical path)