## Sunday, July 23, 2017

### [Leetcode] Alien Dictionary, Solution

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:
Given the following words in dictionary,
```[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
```
The correct order is: `"wertf"`.
Example 2:
Given the following words in dictionary,
```[
"z",
"x"
]
```
The correct order is: `"zx"`.
Example 3:
Given the following words in dictionary,
```[
"z",
"x",
"z"
]
```
The order is invalid, so return `""`.
Note:
1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

[Thoughts]

1. 找出当前入度为0的节点
2. 所有和该节点相连接的节点入度减1
3. go to #1

[Code]
``````1:  string alienOrder(vector<string>& words) {
2:       unordered_map<char, set<char>> outbound;
3:       unordered_map<char, set<char>> inbound;
4:    set<char> no_pre;
5:
6:    string s = "";
7:    for(int i =0; i< words.size(); i++) {
8:      string t = words[i];
9:      no_pre.insert(t.begin(), t.end());
10:      for(int j = 0; j< min(s.size(), t.size()); j++) {
11:        if(t[j] != s[j]) {
12:          inbound[t[j]].insert(s[j]);
13:          outbound[s[j]].insert(t[j]);
14:          break;
15:        }
16:      }
17:      s = t;
18:    }
19:
20:    // get the nodes which has 0 inbound edge
21:    int char_count = no_pre.size();
22:    for(auto p : inbound) {
23:      no_pre.erase(p.first);
24:    }
25:
26:    string result = "";
27:    while(no_pre.size() >0) {
28:      auto it = no_pre.begin();
29:      char c = *it;
30:      no_pre.erase(c);
31:      result+=c;
32:
33:      for(char su : outbound[c]) {
34:        inbound[su].erase(c);
35:        if(inbound[su].size() == 0) {
36:          no_pre.insert(su);
37:        }
38:      }
39:
40:    }
41:       return result.size() == char_count? result : "";
42:  }
``````