/**
* @param {string[]} words
* @return {string}
*/
var alienOrder = function (words) {
let adj = {};
let parents = {};
// Initialize graph
for (let w of words) {
for (let c of w) {
adj[c] = new Set();
parents[c] = 0;
}
}
// Build graph
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i];
const w2 = words[i + 1];
let minLen = Math.min(w1.length, w2.length);
// Invalid prefix case: ["abc", "ab"]
if (
w1.slice(0, minLen) === w2.slice(0, minLen) &&
w1.length > w2.length
) {
return "";
}
for (let j = 0; j < minLen; j++) {
if (w1[j] !== w2[j]) {
if (!adj[w1[j]].has(w2[j])) {
adj[w1[j]].add(w2[j]);
parents[w2[j]] += 1;
}
break;
}
}
}
// Kahn's Topological Sort
let q = [];
for (let c in parents) {
if (parents[c] === 0) {
q.push(c);
}
}
let res = [];
while (q.length) {
const current = q.pop();
res.push(current);
for (let n of adj[current]) {
parents[n] -= 1;
if (parents[n] === 0) {
q.push(n);
}
}
}
// Cycle detection
if (res.length !== Object.keys(parents).length) {
return "";
}
return res.join("");
};