# [leetcode] 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 words from the dictionary, wherewords are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

```[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
```

The correct order is: `"wertf"`.

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

For each two adjacent strings str1 and str2, find the first mismatch character str1[i] and str2[i]. Add an directed edge from str1[i] to str2[i] in the graph.

Topological sort the graph.

If the graph contains circle or has no nodes with no incoming edges, return empty string, which means error.

```//Step 1. construct the directed graph
//Step 2. Topological sort

//What is the order of "wr" and "wrd"?
class Node{
private:
char c;
int incomingNum;

public:
unordered_map<char, Node *> next;
Node(char c):c(c), incomingNum(0){}
Node(): incomingNum(0){}//for unordered_map usage
incomingNum++;
}
void minusIncomingNum(){
incomingNum--;
}
int getIncomingNum(){
return incomingNum;
}
char getC(){
return c;
}
};
class Solution {
public:
string alienOrder(vector<string>& words) {
string ans;
unordered_map<char, int> letters;
unordered_map<char, Node> graph;
if(words.size() == 0) return ans;
//collect all availiable letters
for(auto it = words.begin(); it != words.end(); it++){
for(auto is = (*it).begin(); is != (*it).end(); is++){
letters[*is] = 1;
}
}
//construct the directed graph
for(size_t i = 0; i + 1 < words.size(); i++){
string str1 = words[i];
string str2 = words[i + 1];
for(size_t j = 0; j < min(str1.size(), str2.size()); j++){
if(str1[j] != str2[j]){
//first mismatch char
char thisc = str1[j];
char nextc = str2[j];
if(graph.find(thisc) == graph.end()){
//meet a new node
graph[thisc] = Node(thisc);
}
if(graph.find(nextc) == graph.end()){
//meet a new node
graph[nextc] = Node(nextc);
}
if(graph[thisc].next.find(nextc) == graph[thisc].next.end()){
//edge not exsit before
graph[thisc].next[nextc] = &graph[nextc];
}
break;//BUG HERE, remember to break
}
}
//code would run into this line if str1 looks like "asfd" and str2 looks like "asfds"

}
//Topologically sort the graph
//find all nodes with no incoming edges
queue<Node *> startNodes;
for(auto it = graph.begin(); it != graph.end(); it++){
if(it->second.getIncomingNum() == 0){
startNodes.push(&(it->second));
}
}
if(startNodes.size() == 0 && graph.size() > 0){
return "";//error, circle in the graph
}
//Topological sort
while(startNodes.empty() != true){
Node * p = startNodes.front();
startNodes.pop();
//push current node to result string
ans.push_back(p->getC());

for(auto it = p->next.begin(); it != p->next.end(); it++){
Node * np = it->second;
np->minusIncomingNum();
if(np->getIncomingNum() == 0){
startNodes.push(np);
}
}
}
//Check if there are edges in graph, circle exist
for(auto it = graph.begin(); it != graph.end(); it++){
if(it->second.getIncomingNum() != 0){
return "";
}
}
for(size_t i = 0; i < ans.size(); i++){
letters[ans[i]] = 0;
}
for(auto it = letters.begin(); it != letters.end(); it++){
if(it->second == 1){
//letter appeared in dict but not in the graph
ans.push_back(it->first);
}
}
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.