forked from MaskRay/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
alien-dictionary.cc
38 lines (38 loc) · 854 Bytes
/
alien-dictionary.cc
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
// Alien Dictionary
class Solution {
public:
string alienOrder(vector<string>& words) {
bool f[26] = {};
int d[26] = {}, top = -1, ab = 0;
vector<int> e[26];
for (auto &w: words)
for (auto c: w)
f[c-'a'] = true;
for (int i = 1; i < words.size(); i++) {
string &x = words[i-1], &y = words[i];
int j = 0;
while (x[j] == y[j] && x[j])
j++;
if (x[j] && y[j]) {
e[x[j]-'a'].push_back(y[j]-'a');
d[y[j]-'a']++;
}
}
string r;
for (int i = 0; i < 26; i++)
if (f[i]) {
ab++;
if (! d[i])
d[i] = top, top = i;
}
while (top != -1) {
int x = top;
top = d[x];
r.push_back('a'+x);
for (auto y: e[x])
if (! --d[y])
d[y] = top, top = y;
}
return r.size() < ab ? "" : r;
}
};