Alien dictionary — order of letters

Hard

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: ""

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 : '';
}