-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.ts
90 lines (74 loc) · 2.5 KB
/
index.ts
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
81
82
83
84
85
86
87
88
89
90
export default function alienOrder(words: string[]): string {
const { edges, indegrees, valid, chars } = createEdgesAndIndegrees(words);
if (!valid) return "";
const order = topologicalsort(edges, indegrees, chars);
return order.length === chars.size ? order.join("") : "";
}
function createEdgesAndIndegrees(words: string[]): {
edges: Map<string, Set<string>>;
indegrees: Map<string, number>;
valid: boolean;
chars: Set<string>;
} {
const chars: Set<string> = new Set();
let valid = true;
const edges = new Map<string, Set<string>>();
const indegrees = new Map<string, number>();
for (const word of words) {
Array.prototype.forEach.call(word, (c: string) => {
chars.add(c);
});
}
for (let i = 0, j = 1; i < words.length && j < words.length; i++, j++) {
const word1 = words[i];
const word2 = words[j];
if (word1.startsWith(word2) && word2.length < word1.length) {
valid = false;
return { valid, edges, indegrees, chars };
}
for (let k = 0; k < word1.length && k < word2.length; k++) {
const char1 = word1[k];
const char2 = word2[k];
if (char1 !== char2) {
edges.set(char1, (edges.get(char1) || new Set()).add(char2));
break;
}
}
}
const parents = new Map<string, Set<string>>();
for (const [parent, children] of edges) {
for (const child of children) {
parents.set(child, (parents.get(child) || new Set()).add(parent));
}
}
parents.forEach((p, child) => {
indegrees.set(child, p.size);
});
return { valid, edges, indegrees, chars };
}
function topologicalsort(
edges: Map<string, Set<string>>,
indegrees: Map<string, number>,
chars: Set<string>,
): string[] {
const order: string[] = [];
let queue = [...chars.keys()].filter((key) => !indegrees.has(key));
while (queue.length) {
const temp: string[] = [];
for (const char of queue) {
order.push(char);
const children = edges.get(char);
if (children) {
for (const child of children) {
const indegree = -1 + (indegrees.get(child) ?? 0);
indegrees.set(child, indegree);
if (indegree === 0) {
temp.push(child);
}
}
}
}
queue = temp;
}
return order;
}