Alien Dictionary
Recover the letter order of an alien alphabet from a sorted word list: compare neighbouring words for facts, then topologically sort the letters.
Problem Understanding
Alien Dictionary: an alien language uses the English letters in an unknown order. You get a list of its words sorted in that language's dictionary order. Return a string of its letters in a valid order, or "" if the list contradicts itself.
Example: ["wrt", "wrf", "er", "ett", "rftt"] returns "wertf".
The Intuition: Facts, Then a Topological Sort
Sorted words hide facts about letters. Compare two neighbours: at the first position where they differ, the upper word's letter must come before the lower word's. Nothing after that position tells you anything.
wrtvswrf: they differ at position 2, sotbeforef.wrfvser: they differ at position 0, sowbeforee.
Each fact is a directed edge. Putting all the letters in an order that respects every edge is exactly a topological sort, and Kahn's algorithm also reports a cycle when the facts contradict each other.
Interactive Walkthrough
The word list is on the left; each adjacent pair is compared in turn, with its first differing letters picked out, and every new fact appears as an edge in the letter graph. Then Kahn's algorithm takes letters with nothing left before them, one at a time.
Dry Run Table
Input: ["wrt", "wrf", "er", "ett", "rftt"]
| Pair | First difference | Fact |
|---|---|---|
| wrt / wrf | position 2 | t → f |
| wrf / er | position 0 | w → e |
| er / ett | position 1 | r → t |
| ett / rftt | position 0 | e → r |
Only w has nothing before it. Kahn's algorithm then places w, e, r, t, f: "wertf".
The Solution Template
Build the letter graph from adjacent pairs, then Kahn's algorithm. The C and C++ versions keep letters in alphabetical order, so where several orders are valid they may return a different one; any valid order is accepted.
Alien Dictionary Code
1var alienOrder = function(words) {2 const graph = new Map(), indegree = new Map();3 for (const w of words) {4 for (const c of w) {5 if (!graph.has(c)) { graph.set(c, []); indegree.set(c, 0); }6 }7 }8 for (let i = 0; i + 1 < words.length; i++) {9 const a = words[i], b = words[i + 1];10 const len = Math.min(a.length, b.length);11 let j = 0;12 while (j < len && a[j] === b[j]) j++;13 if (j === len) {14 if (a.length > b.length) return '';15 continue;16 }17 const x = a[j], y = b[j];18 if (!graph.get(x).includes(y)) {19 graph.get(x).push(y);20 indegree.set(y, indegree.get(y) + 1);21 }22 }23 const queue = [...indegree.keys()].filter((c) => indegree.get(c) === 0);24 const order = [];25 while (queue.length) {26 const c = queue.shift();27 order.push(c);28 for (const next of graph.get(c)) {29 indegree.set(next, indegree.get(next) - 1);30 if (indegree.get(next) === 0) queue.push(next);31 }32 }33 return order.length === indegree.size ? order.join('') : '';34};
Edge Cases & Common Mistakes
- A longer word before its prefix:
["abc", "ab"]is impossible in any alphabet; return""straight away. - A prefix before the longer word:
["ab", "abc"]is fine and gives no fact. - Looking past the first difference: only the first differing position is a fact; later letters are unordered.
- Letters with no facts: they still belong in the answer, so add every letter as a node before comparing.
- Duplicate facts: adding the same edge twice inflates an in-degree, and that letter never reaches 0.
Summary
Alien Dictionary turns sorted words into a graph: each adjacent pair gives at most one edge, at its first difference. A topological sort of the letters is the alphabet, and a cycle or a word before its own prefix means there is none.
More practice: DSA interview questions with answers · patterns cheat sheet