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
| class Solution {
int N = 26, M = N * N, idx = 0, cnt = 0;
int[] he = new int[N], e = new int[M], ne = new int[M];
int[] in = new int[N], out = new int[N];
boolean[] visited = new boolean[N];
private void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
++out[a];
++in[b];
}
public String alienOrder(String[] words) {
int n = words.length;
Arrays.fill(he, -1);
for (int i = 0; i < n; ++i) {
for (char c : words[i].toCharArray()) {
if (!visited[c - 'a']) {
visited[c - 'a'] = true;
++cnt;
}
}
for (int j = 0; j < i; ++j) {
if (!build(words[j], words[i])) return "";
}
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < 26; ++i) {
if (visited[i] && in[i] == 0) queue.offer(i);
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
int cur = queue.poll();
sb.append((char) (cur + 'a'));
for (int i = he[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (--in[j] == 0) queue.offer(j);
}
}
return sb.length() == cnt ? sb.toString() : "";
}
private boolean build(String a, String b) {
int m = a.length(), n = b.length();
for (int i = 0; i < Math.min(m, n); ++i) {
int c1 = a.charAt(i) - 'a', c2 = b.charAt(i) - 'a';
if (c1 != c2) {
add(c1, c2);
return true;
}
}
return m <= n;
}
}
|
wechat
