Alien Dictionary
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
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
题意 题目定义了一个新的字母先后顺序。给出了几个sample，问是否能推断出所有字母的先后顺序。如果字母推断有相互矛盾的地方，就返回空串。 这是一个典型的 建图 + 拓扑排序。
代码
class Solution {
public String alienOrder(String[] words) {
List<char[]> relations = new ArrayList<>();
int[] degree = new int[26];
Arrays.fill(degree, -1);
for(String s : words) {
for(char c : s.toCharArray()) {
degree[c -'a'] = 0;
}
}
for(int i = 0; i < words.length - 1; i++) {
int j = i+1, len = Math.min(words[i].length(), words[j].length());
int k = 0;
for( k = 0; k < len; k++) {
if(words[i].charAt(k) != words[j].charAt(k)) {
relations.add(new char[]{words[i].charAt(k), words[j].charAt(k)});
degree[words[j].charAt(k) - 'a']++;
break;
}
}
if(k == len && words[i].length() > words[j].length()) return "";
}
//bfs part
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < degree.length; i++) {
if(degree[i] == 0) {
queue.add(i);
degree[i] = -1;
}
}
String ret = "";
while(!queue.isEmpty()) {
int cur = queue.poll();
ret += (char)(cur + 'a')+ "";
for(int i = 0; i < relations.size(); i++) {
if(relations.get(i)[0] == (cur + 'a')) degree[relations.get(i)[1] - 'a']--;
}
for(int i = 0; i < degree.length; i++) {
if(degree[i] == 0) {
queue.add(i);
degree[i] = -1;
}
}
}
for(int i = 0; i < degree.length; i++) {
if(degree[i] != -1) return "";
}
return ret;
}
}