还是先抄一下题目:
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 "".
Note:
- You may assume all letters are in lowercase.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/alien-dictionary
简单说一下思路
今天刷的第二道题目,本质上是一道拓扑排序的题目,只不过需要注意的小细节比较多。(不然怎么是Hard难度)我认为这题的hard难度主要就在与图中的edge需要自己找,也可能会重复,然后节点是用分散的字母而不是连续的数字表示的。
先贴一下代码:
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> graph;
unordered_map<char, int> indegree;
for(auto word:words){
for(auto letter:word){
if(indegree.find(letter)==indegree.end()){
indegree[letter]=0;
graph[letter]=unordered_set<char>();
}
}
}
//build graph
for(int i=0;i+1<words.size();i++){
int j=0;
while(j<words[i].size()&&j<words[i+1].size()&&words[i][j]==words[i+1][j]){
j++;
}
if(j<words[i].size()&&j<words[i+1].size()){
char a = words[i][j];
char b = words[i+1][j];
if(graph[a].count(b)==0){
graph[a].insert(b);
indegree[b]++;
}
}
else{
if(j<words[i].size())return "";
}
}
queue<char> q;
unordered_map<char, int>::iterator iter;
for(iter=indegree.begin();iter!=indegree.end();iter++){
if(iter->second==0) {
q.push(iter->first);
}
}
string ans="";
while(!q.empty()){
char front=q.front();
q.pop();
ans+=front;
for(auto i:graph[front]){
indegree[i]--;
if(indegree[i]==0)q.push(i);
}
}
for(auto kv :indegree){
if(kv.second!=0)return "";
}
return ans;
}
};
这题其实可以和 //www.greatytc.com/p/dc3a1c9cdd3a 题号207的那题做一下对比,题目本质是一样的,只不过这题不太直观,要自己提炼出来才知道啊这原来是一道拓扑排序的题。
此题和207那题的区别是:在这题里,因为node都有char表示,将它重新标号其实有点麻烦也不划算,所以可以直接把图存在unordered_map<char, unordered_set>里,对应的每个node的入度也存在字典里。
这种方法还要注意为了让graph和indegree的size与节点数目相同,还要在开头做一个初始化操作。