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,
Given the following words in dictionary,
[ "wrt", "wrf", "er", "ett", "rftt" ]
The correct order is:
"wertf"
.
Example 2:
Given the following words in dictionary,
Given the following words in dictionary,
[ "z", "x" ]
The correct order is:
"zx"
.
Example 3:
Given the following words in dictionary,
Given the following words in dictionary,
[ "z", "x", "z" ]
The order is invalid, so return
""
.
Note:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- 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: }
No comments:
Post a Comment