269. Alien Dictionary

1function alienOrder(words: string[]): string {
2  const adj = new Map<string, Set<string>>();
3  for (const ch of words.join("")) adj.set(ch, new Set());
4  for (let i = 0; i + 1 < words.length; i++) {
5    const [a, b] = [words[i], words[i + 1]];
6    const k = [...a].findIndex((ch, j) => ch !== b[j]);
7    if (k === -1 || k >= b.length) { if (a.length > b.length) return ""; continue; }
8    adj.get(a[k])!.add(b[k]);
9  }
10  const state = new Map<string, number>(); // 1 = visiting, 2 = done
11  const out: string[] = [];
12  function visit(ch: string): boolean {
13    if (state.get(ch) === 1) return false;
14    if (state.get(ch) === 2) return true;
15    state.set(ch, 1);
16    for (const next of adj.get(ch)!) if (!visit(next)) return false;
17    state.set(ch, 2); out.push(ch);
18    return true;
19  }
20  for (const ch of adj.keys()) if (!visit(ch)) return "";
21  return out.reverse().join("");
22}

Collect every letter as a node.

Space: play/pause · ←/→: step