一、题目描述
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
示例 1：
输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"示例 2：
输入：words = ["z","x"]
输出："zx"示例 3：
输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。提示：
1 <= words.length <= 1001 <= words[i].length <= 100words[i]仅由小写英文字母组成
分析：
根据题意，需要从给出的字符串数组中找出出现字母之间的顺序。
各字符串中在字符串数组words中已经是按递增顺序排列，我们可以通过比较数组中两两相邻的字符串中的对应字符得出字符比较大小的结果。
例如，给定字符串数组words = [“wrt”,”wrf”,”er”,”ett”,”rftt”].
因为words[0] < words[1],可知’t’ < ‘f’;
words[1] < words[2],可知‘w’ < ‘e’;
words[2] < words[3],可知’r’ < ‘t’;后续比较规律相同。
对于此类题应该通过具体的例子抽象出相应规律。
另外通过提交我发现有一个特殊输入words = [“abc”,”ab”]，后一个字符串是前一个字符串的前缀，即前一个字符串长度大于后一个，这就违背了题目说明的字符串数组是递增排列，这就是一个不合法的无效输入，应返回空字符串””.
通过以上分析，我们可以把这个问题抽象成一个图遍历问题，字符表示图节点，排在靠前顺序的字符有一条指向靠后顺序字符的有向边，而最靠前的字符表示入度为0的节点，通过广度优先遍历每次把所有入度为0的节点放进队列，在遍历过程中队列中的节点顺序就是字符之间的相对顺序(之一，因为由给定的条件无法判断唯一顺序，同时拓扑排序如果成功那么也不一定有唯一解)。
明白此问题的算法思想以后，就转换成了建图再BFS遍历的过程。用一个HashMap来表示图节点之间的关系，key表示该字符，value表示顺序排在该字符之后的所有字符，即该字符key有一条指向value中各个字符的有向边，又因为字符不用重复保存，只需一条边表示两个字符之间的关系，我们就用HashSet做value表示该字符集合。这样建立好字符之间的顺序关系以后，由于需要使用拓扑排序，我们还需要用一个数组或者哈希表保存每个字符的入度数量，因为此题输入只有小写字母，只用一个空间为26的数组保存即可。代码如下：
作者：SloanCheng
链接：https://leetcode-cn.com/problems/Jf1JuT/solution/tu-bfstuo-bu-pai-xu-suan-fa-by-sloanchen-08qb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码提示：
class Solution {
public:
int startsWith(string s, string sub) {
return s.find(sub) == 0 ? 1 : 0;
}
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> graph;
unordered_map<char, int> inDegree;
string res;
for(int i=0; i<words.size(); ++i){
for(char ch:words[i]){
graph[ch] = {};
inDegree[ch] = 0;
}
}//先把构建图用的坑位占好
for(int i=0; i<words.size()-1; ++i){
string first = words[i];
string second = words[i+1];
// 1以2为前缀开头，2还比1短，不符合字典的短在长的前面原则。
if(startsWith(first,second) && first.size() > second.size()){
return "";
}
for(int j=0; j<first.size() && j<second.size(); ++j){
char ch1 = first[j];
char ch2 = second[j];
//找到两个单词中，第一个: 字符不同的位置，构造成前面单词中这个位置字母，指向后者对应位置字母。
if(ch1 != ch2){
if(!graph[ch1].count(ch2)){
graph[ch1].insert(ch2);
inDegree[ch2]++;
}
break;//一旦找到第一个不同的位置，记录下一对先后关系。这两个单词就没有利用价值了。
}
}
}
//下面就是把构造好的图，用图中指定的先后关系来输出每个图的顶点。就是想要的结果。
//也就是拓扑排序，这里使用队列来把没有依赖关系的顶点先输出。还有另外一种方法，用dfs输出拓扑顺序。
queue<char> que;
for(auto ch:inDegree){
if(ch.second == 0)
que.push(ch.first);
}
while(!que.empty()){
char ch = que.front(); que.pop();
res+=ch;
for(char next:graph[ch]){
inDegree[next]--;
if(inDegree[next]==0)
que.push(next);
}
}
//如果输出的所有结果数量不等于图中顶点的数量，说明图中有环出现
//也就是给定的字母先后关系中（打乱了该有的先后顺序，有排在后面的字母，指向了前面的字母。）
return res.size() != inDegree.size()? "":res;
}
};喜欢算法的攻城狮们，可以用搜索引擎，搜索力扣官网，进行锻炼学习算法提升自己,大佬留个赞。