一、题目
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
示例 1：
输入：words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
输出：“wertf”
示例 2：
输入：words = [“z”,“x”]
输出：“zx”
示例 3：
输入：words = [“z”,“x”,“z”]
输出：“”
解释：不存在合法字母顺序，因此返回 “” 。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
二、题解
class Solution {
public:
string alienOrder(vector<string>& words) {
int n = words.size();
vector<int> indegree(26,-1);
vector<vector<int>> graph;
for(auto w:words){
for(int i = 0;i < w.size();i++){
indegree[w[i] - 'a'] = 0;
}
}
int cnt = 0;
for(int i = 0;i < 26;i++){
if(indegree[i] == 0) cnt++;
}
for(int i = 0;i < 26;i++){
graph.push_back({
});
}
for(int i = 0;i < n - 1;i++){
string cur = words[i];
string next = words[i+1];
int len = min(cur.size(),next.size());
int j = 0;
for(;j < len;j++){
if(cur[j] != next[j]){
graph[cur[j] - 'a'].push_back(next[j] - 'a');
indegree[next[j] - 'a']++;
break;
}
}
if(j < cur.size() && j == next.size()) return "";
}
string res = "";
queue<int> q;
for(int i = 0;i < 26;i++){
if(indegree[i] == 0) q.push(i);
}
while(!q.empty()){
int e = q.front();
q.pop();
res.push_back('a' + e);
int size = graph[e].size();
for(int i = 0;i < size;i++){
indegree[graph[e][i]]--;
if(indegree[graph[e][i]] == 0) q.push(graph[e][i]);
}
}
if(res.size() == cnt) return res;
else return "";
}
};
