题目大意：
火星词典
现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。您有一个单词列表（从词典中获得的），该单词列表内的单词已经按这门新语言的字母顺序进行了排序。需要根据这个输入的列表，还原出此语言中已知的字母顺序。
示例1:
输入:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
输出: "wertf"示例2:
输入:
[
"z",
"x"
]
输出: "zx"
示例3:
输入: [ "z", "x", "z" ] 输出:""解释: 非法排序， 返回"".
提示:
- 所有字母都是小写字母.
- 如果a在b的前面，字典中a应该出现在b的前方
- 如果是非法顺序，返回空
- 返回任意一种合理排序
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=269
解题思路分析：
这道题与之前分享过的一题非常相似，那道题是安排选修课，每种选修课可能会存在一些先修课程，本题字典顺序排序也完全可以将排在前面的字母看做是其后面字母的先修课。如果没有做过之前那道题，强烈推荐先看懂下面两篇关于选修课题目的文章，文章中详细介绍了如何使用拓扑排序方式来解题。看懂算法之后再来做本题就会轻松很多，也同时可以利用本题来作为练手。
LEETCODE 207. Course Schedule解题思路分析
LEETCODE 210. Course Schedule II解题思路分析
本题相对选修课那题比较稍微复杂一些，复杂的地方在于题目中并没有给出”先修课”(排在当前字母前面字母)列表，这需要我们自行构建出该关系图，构建后利用拓扑排序解题即可。
构建关系图时，我们要利用题目给出的words数组，由于数组中单词已经按照字典顺序排序好，因此，我们可以对相邻的两两单词进行比较，从两个单词的第一位开始对比，如果字符相同就移动到下一位，如果不同，前面单词的当前字母应该排在后一单词当前字母的前面，也就是说前字母是后字母的”先修课”。比如ab和ac，第一位两个a相同，继续看第二位，b和c不同，因为b所在的单词字典顺序靠前，因此b应排在c的前面。我们利用一个Map保存统计结果，key为相对靠前的字母，value为所有排在该字母后方的字母的集合。
map建立好之后，利用拓扑排序思想解题即可。
实现代码：
// 用于统计排在每种字母后面的所有字母
Map<Character, List<Character>> map = new HashMap<>();
// 拓扑排序用的访问数组
int[] visited = new int[26];
// 用于统计words中存在哪些字母
boolean[] has = new boolean[26];
public String alienOrder(String[] words) {
// 统计words中存在哪些字母
for(int i=0;i<words.length;i++){
String current=words[i];
for(int j=0;j<current.length();j++){
has[current.charAt(j)-'a']=true;
}
}
// 相邻2单词比较，统计排在每种字母后面的所有字母
for(int i=1;i<words.length;i++){
// 前单词
String pre = words[i-1];
// 当前单词
String current=words[i];
// 单词下标
int index=0;
// 比较2单词同一下标
while(index<pre.length() && index<current.length()){
// 前单词当前字符
char p = pre.charAt(index);
// 当前单词当前字符
char c = current.charAt(index);
// 2字符不同
if(p!=c){
// 将当前字母放入前字母的后续列表中
List<Character> l=map.getOrDefault(p,new ArrayList<>());
l.add(c);
map.put(p, l);
break;
}
index++;
}
}
// 返回结果
String res="";
// 循环dfs每种字符
for(int i=0;i<26;i++){
// 如果该字母没有出现过，跳过
if(!has[i]) continue;
// 如果存在非法排序，返回空
if(!dfs((char)(i+'a'))) return res;
}
// 因为拓扑排序是反向遍历，所以将结果倒序打印出来。
for(int i=resList.size()-1;i>=0;i--){
res+=resList.get(i);
}
return res;
}
List<Character> resList = new ArrayList<>();
// 拓扑排序（dfs）
boolean dfs(char c){
if(visited[c-'a']==1) return false;
if(visited[c-'a']==2) return true;
visited[c-'a']=1;
List<Character> list = map.get(c);
if(list!=null) {
for(Character next : list){
if(!dfs(next)) return false;
}
}
visited[c-'a']=2;
resList.add(c);
return true;
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 93.15% of Java online submissions for Alien Dictionary.
Memory Usage: 35.6 MB, less than 97.30% of Java online submissions for Alien Dictionary.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-269-alien-dictionary-解题思路分析/