Alien dictionary — order of letters
Problem
An alien language uses English letters in an unknown order. Given a list of words sorted in that language's order, deduce an order of the letters that is consistent with it, or return "" if the list is contradictory.
Example 1
Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"
Also asked as: Given a sorted Dictionary of an Alien Language, find order of characters
Test cases
Case 1
Input: ["wrt","wrf","er","ett","rftt"] Expected: "wertf"
Case 2
Input: ["z","x"] Expected: "zx"
Case 3
Input: ["z","x","z"] Expected: ""
Case 4
Input: ["abc","ab"] Expected: ""
View solutionHide solution1 approach
1. Build a precedence graph from adjacent words, topological sort
Time O(total chars)Space O(1) — 26 letters
For each adjacent pair of words, the first differing character gives an edge a → b. Topologically sort the letters. A prefix that comes after its extension is invalid.
function alienOrder(words) { const adj = new Map(), indeg = new Map(); for (const w of words) for (const c of w) { adj.set(c, adj.get(c) || new Set()); indeg.set(c, 0); } for (let i = 0; i + 1 < words.length; i++) { const a = words[i], b = words[i + 1]; if (a.length > b.length && a.startsWith(b)) return ''; for (let j = 0; j < Math.min(a.length, b.length); j++) { if (a[j] !== b[j]) { if (!adj.get(a[j]).has(b[j])) { adj.get(a[j]).add(b[j]); indeg.set(b[j], indeg.get(b[j]) + 1); } break; } } } const q = [...indeg].filter(([, d]) => d === 0).map(([c]) => c); let order = ''; for (let i = 0; i < q.length; i++) { order += q[i]; for (const nb of adj.get(q[i])) if (indeg.set(nb, indeg.get(nb) - 1).get(nb) === 0) q.push(nb); } return order.length === indeg.size ? order : '';}