Twitter电面

互相自我介绍，然后聊了聊简历中的一个项目, 最后就一道题 alien dictionary. 感觉这道题出现的频率蛮高的～

关注一亩三分地公众号：
Warald_一亩三分地

请问lz的alien dictionary能详细讲讲么， 一直看到有人po 这题，却不知道出处在那里＝＝

关注一亩三分地微博：
Warald

电面面alien dictionary。。。

1. class Solution {
   
2. public:
   
3.     string alienOrder(vector<string>& words) {
   
4.         if(words.size() == 1) return words[0];
   
5.         graph g = makeGraph(words);
   
6.         return sort(g);
   
7.     }
   
8. private:
   
9.     typedef unordered_map<char, unordered_set<char>> graph;
   
10.    
    
11.     graph makeGraph(vector<string> words) {
    
12.         graph g;
    
13.         for(int i = 1; i < words.size(); ++i) {
    
14.             bool found = false;
    
15.             string word1 = words[i - 1];
    
16.             string word2 = words[i];
    
17.             int len1 = word1.size(), len2 = word2.size();
    
18.             int l = max(len1, len2);
    
19.             for(int j = 0; j < l; ++j) {
    
20.                 if(j < len1 && g.find(word1[j]) == g.end()) {
    
21.                     g[word1[j]] = unordered_set<char>();
    
22.                 }
    
23.                 if(j < len2 && g.find(word2[j]) == g.end()) {
    
24.                     g[word2[j]] = unordered_set<char>();
    
25.                 }
    
26.                 if(j < len1 && j < len2 && word1[j] != word2[j] && found == false) {
    
27.                     g[word1[j]].insert(word2[j]);
    
28.                     found = true;
    
29.                 }
    
30.             }
    
31.         }
    
32.         return g;
    
33.     }
    
34.     string sort(graph g) {
    
35.         string topo = "";
    
36.         vector<bool> visited(256, false), path(256, false);
    
37.         for(auto node : g) {
    
38.             if(!acyclic(g, node.first, visited, path, topo)) {
    
39.                 return "";
    
40.             }
    
41.         }
    
42.         reverse(topo.begin(), topo.end());
    
43.         return topo;
    
44.     }
    
45.    
    
46.     bool acyclic(graph g, char node, vector<bool> &visited, vector<bool> &path, string &topo) {
    
47.         if(path[node]) return false;
    
48.         if(visited[node]) return true;
    
49.         path[node] = visited[node] = true;
    
50.         for(auto n : g[node]) {
    
51.             if(!acyclic(g, n, visited, path, topo)) return false;
    
52.         }
    
53.         path[node] = false;
    
54.         topo.push_back(node);
    
55.         return true;
    
56.     }
    
57.    
    
58. };

复制代码

zzx04025 发表于 2016-3-28 08:14
请问lz的alien dictionary能详细讲讲么， 一直看到有人po 这题，却不知道出处在那里＝＝

http://blog.csdn.net/pointbreak1/article/details/48761705
http://www.cnblogs.com/jcliBlogger/p/4758761.html