Alien Dictionary
HardGraphs
An alien language writes with lowercase English letters, but orders them differently. You get a list of its words, already sorted the way its dictionary sorts them: by the first letter where two words differ, and a word before any longer word it is the start of.
Return a string that holds every letter used in the words exactly once, in an order that fits the list. When several orders fit, any of them is accepted.
If no order fits, return "". That happens when the list contradicts itself, or when a word comes before a shorter word that is its own start, such as "abc" before "ab".
Examples
Input: words = ["cab", "cad", "bd", "bda", "da"] Output: "acbd"
cab before cad puts b before d, and cad before bd puts c before b. Nothing places a, so "cbda" or "cabd" are right too.
Input: words = ["ba", "ab", "bb"] Output: ""
The first pair puts b before a and the second puts a before b, so no order fits.
Constraints
1 ≤ words.length ≤ 1001 ≤ words[i].length ≤ 100- Words use lowercase English letters only.
Stuck?
Hint 1
Only neighbors in the list tell you anything, and only at the first letter where they differ: that letter comes before the other. These rules are arrows between letters, and the answer is a topological order of them.
Hint 2
Collect the arrows (once each), then run Kahn’s algorithm from the letters nothing points to. If some letters never come out, the arrows loop and the answer is "". Check for a longer word listed before its own prefix before anything else.
The idea
In a sorted list, two neighbouring words are ordered by the first letter where they differ, so that letter comes before the other. Each such pair is an arrow from one letter to another, and any order that keeps every arrow pointing forward is an answer: a topological sort. If the arrows form a loop, no order fits.
Time O(C) for C letters in all the wordsExtra space O(1): at most 26 letters and 26² arrows
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
after maps each letter to the letters that must come after it, and before counts the arrows pointing into each letter. Every letter in the words goes in, even one no rule mentions, because the answer must hold every letter.
function alienOrder(words) { const after = new Map(); const before = new Map(); for (const word of words) { for (const ch of word) { if (!after.has(ch)) { after.set(ch, new Set()); before.set(ch, 0); } } } for (let i = 1; i < words.length; i++) { const a = words[i - 1]; const b = words[i]; let j = 0; while (j < a.length && j < b.length && a[j] === b[j]) j++; if (j === b.length && a.length > b.length) return ''; if (j < a.length && j < b.length && !after.get(a[j]).has(b[j])) { after.get(a[j]).add(b[j]); before.set(b[j], before.get(b[j]) + 1); } } const queue = [...before.keys()].filter((ch) => before.get(ch) === 0); let order = ''; while (queue.length) { const ch = queue.shift(); order += ch; for (const next of after.get(ch)) { before.set(next, before.get(next) - 1); if (before.get(next) === 0) queue.push(next); } } return order.length === after.size ? order : '';}The trap
This version leaves out the check for a word placed before its own prefix, such as abc before ab. Those two words add no arrow, so the sort runs and returns an order. But no order can put a word after a longer word that starts with it, so any such list gets a string where '' was due.
function alienOrder(words) { const after = new Map(); const before = new Map(); for (const word of words) { for (const ch of word) { if (!after.has(ch)) { after.set(ch, new Set()); before.set(ch, 0); } } } for (let i = 1; i < words.length; i++) { const a = words[i - 1]; const b = words[i]; let j = 0; while (j < a.length && j < b.length && a[j] === b[j]) j++; // never notices a longer word listed before its own prefix if (j < a.length && j < b.length && !after.get(a[j]).has(b[j])) { after.get(a[j]).add(b[j]); before.set(b[j], before.get(b[j]) + 1); } } const queue = [...before.keys()].filter((ch) => before.get(ch) === 0); let order = ''; while (queue.length) { const ch = queue.shift(); order += ch; for (const next of after.get(ch)) { before.set(next, before.get(next) - 1); if (before.get(next) === 0) queue.push(next); } } return order.length === after.size ? order : '';}