Given a list of words (Strings), generate the order of the language. If the given input is invalid you can return an empty string (”). Sometimes, multiple orders are possible. The following approach uses Topological Sort and DFS (Depth First Search).
const buildAdjacencyList = (wordList, adjacencyList) => {
for (const word of wordList) {
for (let i = 0; i < word.length; i++) {
if (!adjacencyList.has(word.charAt(i))) {
adjacencyList.set(word.charAt(i), []);
}
}
}
for (let i = 0; i < wordList.length - 1; i++) {
const firstWord = wordList[i];
const secondWord = wordList[i + 1];
if (firstWord.startsWith(secondWord) && firstWord.length > secondWord.length) {
return false;
}
const minLen = Math.min(firstWord.length, secondWord.length);
for (let j = 0; j < minLen; j++) {
const firstWordChar = firstWord.charAt(j);
const secondWordChar = secondWord.charAt(j);
if (firstWordChar !== secondWordChar) {
// Store in reverse to get the correct order in the end.
adjacencyList.get(secondWordChar).push(firstWordChar);
break;
}
}
}
return true;
};
const topologicalSort = (currChar, adjacencyList, visited, resultStack) => {
if (!(currChar in visited)) {
visited[currChar] = false;
if (adjacencyList.has(currChar)) {
for (const char of adjacencyList.get(currChar)) {
const result = topologicalSort(char, adjacencyList, visited, resultStack);
if (!result) return false;
}
}
visited[currChar] = true;
resultStack.push(currChar);
return true;
} else {
return visited[currChar];
}
};
var alienOrder = function(words) {
const adjacencyList = new Map();
const valid = buildAdjacencyList(words, adjacencyList);
if (!valid) {
return '';
}
const resultStack = [];
const visited = {};
for (const [key, value] of adjacencyList) {
const result = topologicalSort(key, adjacencyList, visited, resultStack);
if (!result) {
return '';
}
};
if (resultStack.length !== adjacencyList.size) {
return '';
}
return resultStack.join('');
};
console.log(alienOrder(['dog', 'dot', 'dotted']));
// "dogte"