-
Notifications
You must be signed in to change notification settings - Fork 0
/
alien-dictionary.js
80 lines (64 loc) · 2.68 KB
/
alien-dictionary.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
// You are given a list of strings words from the alien language's dictionary where the strings in words are sorted lexicographically by the rules of this new language.
// Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "".
// If there are multiple solutions, return any of them.
// A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language.
// If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.
// --- Examples
// Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
// Output: "wertf"
/**
*
* @param {string[]} words
* @returns {string}
*/
function alienOrder(words) {
const neighborCharsOf = {};
for (const word of words) {
for (const char of word) {
if (!(char in neighborCharsOf)) {
neighborCharsOf[char] = new Set();
}
}
}
for (let wordIndex = 0; wordIndex < words.length - 1; wordIndex++) {
const word1 = words[wordIndex];
const word2 = words[wordIndex + 1];
const substringLength = Math.min(word1.length, word2.length);
const haveSameSubstring =
word1.substring(0, substringLength) ===
word2.substring(0, substringLength);
if (haveSameSubstring && word1.length > word2.length) return "";
if (!haveSameSubstring) {
for (let charIndex = 0; charIndex < substringLength; charIndex++) {
const char1 = word1[charIndex];
const char2 = word2[charIndex];
if (char1 !== char2) {
neighborCharsOf[char1].add(char2);
break;
}
}
}
}
const visitedChars = {};
const reverseOrderedChars = [];
function dfs(char) {
if (char in visitedChars) {
return visitedChars[char];
}
// mark the current character true to indicate it's been visited and it's in the current path
visitedChars[char] = true;
for (const neighborChars of neighborCharsOf[char]) {
if (dfs(neighborChars)) return true;
}
// mark it false after the loop to mark it's no longer in the current path
visitedChars[char] = false;
reverseOrderedChars.push(char);
}
for (const char of Object.keys(neighborCharsOf)) {
if (dfs(char)) return "";
}
// reverse the array to produce the correct order and join them into a string before returning it
return reverseOrderedChars.reverse().join("");
}
console.log(alienOrder(["wrt", "wrf", "er", "ett", "rftt"]));