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
| class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> nodeNeighbor = new HashMap<>();
Map<Character, Integer> inDegreeCount = new HashMap<>();
Set<Character> letterSet = new HashSet<>();
addLetter(words[0], letterSet);
for (int i = 1; i < words.length; i++) {
addLetter(words[i], letterSet);
int diffPos = findDiffPos(words[i - 1], words[i]);
if (diffPos != -1) {
char smallerLetter = words[i - 1].charAt(diffPos), biggerLetter = words[i].charAt(diffPos);
if (!nodeNeighbor.containsKey(smallerLetter)
|| !nodeNeighbor.get(smallerLetter).contains(biggerLetter)) {
nodeNeighbor.computeIfAbsent(smallerLetter, (key) -> new HashSet<>()).add(biggerLetter);
inDegreeCount.put(biggerLetter, inDegreeCount.getOrDefault(biggerLetter, 0) + 1);
}
} else if (words[i].length() < words[i - 1].length()) {
return "";
}
}
StringBuilder alienOrder = new StringBuilder();
Deque<Character> nodes = new ArrayDeque<>();
for (char letter : letterSet) {
if (!inDegreeCount.containsKey(letter)) {
nodes.offer(letter);
}
}
while (!nodes.isEmpty()) {
char currLetter = nodes.poll();
alienOrder.append(currLetter);
if (nodeNeighbor.containsKey(currLetter)) {
for (char neighbor : nodeNeighbor.get(currLetter)) {
inDegreeCount.put(neighbor, inDegreeCount.get(neighbor) - 1);
if (inDegreeCount.get(neighbor) == 0) {
nodes.offer(neighbor);
}
}
}
}
return alienOrder.length() == letterSet.size() ? alienOrder.toString() : "";
}
private int findDiffPos(String str1, String str2) {
if (str1.equals(str2))
return -1;
if (str1.length() > str2.length())
return findDiffPos(str2, str1);
int ptr1 = 0, ptr2 = 0;
while (ptr1 < str1.length() && str1.charAt(ptr1) == str2.charAt(ptr2)) {
ptr1 += 1;
ptr2 += 1;
}
return ptr1 == str1.length() ? -1 : ptr1;
}
private void addLetter(String word, Set<Character> letterSet) {
for (char letter : word.toCharArray()) {
letterSet.add(letter);
}
}
}
|
拓扑排序的经典题.
这里就是相邻两个word比较, 找出第一个不一样letter的位置, 此时靠前的word的这个位置的letter就靠前, 靠后的word的这个位置的letter就靠后. 出现两个word一模一样或者一个word是另一个word的substring的时候, 返回-1.
需要注意三个点. 第一个是每个字母都是一个node, 小的字母指向大的字母. 第二是edge不要重复算, 如果之前遇到过node1 -> node2, 那么再遇到的时候就不要重复计算. 第三是如果出现一个string是另一个substring的情况, 要保证靠后的string是较长的string.
时间复杂度: O(ns)
空间复杂度: O(ns)
