There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input:
[
"z",
"x",
"z"
]
Output: ""
Explanation: The order is invalid, so return "".
/**
1. "按这门新语言的字母顺序进行了排序" 这句很重要, 意思是相邻两个word 的第一个不同字符代表了相对顺序!
2. 图论问题怎么建图是一个难点, 建图后拓扑排序即可, 有环输出空字符串
*/
class Solution {
static final int BASE = 26;
public String alienOrder(String[] words) {
Map<Character, Integer> loc = new HashMap<>();
Map<Integer, Integer> ins = new TreeMap<>();
List<Character> list = new ArrayList<>();
List<List<Integer>> graph = new ArrayList<>();
while (graph.size() < BASE) graph.add(new ArrayList<>());
for (int i = 0; i < words.length; i++){
String word = words[i];
for (int j = 0; j < word.length(); j++){
char c = word.charAt(j);
if (loc.get(c) == null){
list.add(c);
int index = list.size()-1;
loc.put(c, index);
if (ins.get(index) == null) ins.put(index, 0);
}
}
}
for (int i = 0 ; i < words.length -1 ; i++){
String word = words[i];
String next = words[i+1];
for (int j = 0 ; j < word.length() && j < next.length(); j++){
int x = loc.get(word.charAt(j));
int y = loc.get(next.charAt(j));
if (x != y){
graph.get(x).add(y);
ins.put(y, ins.get(y) + 1);
break;
}
}
}
String result = topSort(graph, list, ins);
return result;
}
public String topSort(List<List<Integer>> graph, List<Character> list, Map<Integer, Integer> ins){
Queue<Integer> queue = new LinkedList<>();
for (Integer i : ins.keySet()){
if (ins.get(i) == 0){
queue.offer(i);
}
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()){
int top = queue.poll();
result.add(top);
List<Integer> edge = graph.get(top);
for (int i = 0 ; i < edge.size() ; i++){
int next = edge.get(i);
ins.put(next, ins.get(next)-1);
if (ins.get(next) == 0) queue.offer(next);
}
}
if(list.size() != result.size()) return "";
return result.stream().map(x->String.valueOf(list.get(x))).collect(Collectors.joining(""));
}
}