Problem:

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:

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.

Solution:

这道题可以分为两部分。

1. 根据单词之间的关系构建拓扑图

　　以第一个例子为例，对每对相邻的两个字符串提取拓扑关系，如“wrt"和"wrf"，找到两个字符串第一个不相同的字符，将t->f插入哈希表，以此类推。注意如果第一个字符串是第二个字符串添加后缀组成的话，则可以直接返回空，如”wrt“和”wr“，因为它不存在拓扑排序的可能性。

2. 利用BFS得到结果

　　这一步是算法核心，难点在于我们不知道哪个字符才是起始点。所以先用一个indegree数组计算每个出现过的字符的入度，如果为0则可以断定它必为起始点，则将它插入队列中，注意可能存在多个起始点。然后利用BFS和第一步得到的拓扑关系，每推出一个字符就将这个字符的所有出度推入队列，如果发现推入的字符已经访问过，则必然存在环，输出空。注意可能存在这种情况，a->b,c->b，如果简单的将出度推入队列则b会推入两次，所以我们只有在indegree['b']为0时才推入队列，否则自减1。

Code:

1 class Solution { 2 public: 3     string alienOrder(vector
       
        & words) { 4         if(words.size() == 0) return ""; 5         if(words.size() == 1) return words[0]; 6         unordered_map
        
         
          > graph; 7         vector
          
            allchar(128,false); 8         for(int i = 1;i != words.size();++i){ 9             string str1 = words[i-1];10             string str2 = words[i];11             int p1 = 0;12             int p2 = 0;13             for(char c:str1) allchar[c] = true;14             for(char c:str2) allchar[c] = true;15             while(p1 != str1.size() && p2 != str2.size() && str1[p1] == str2[p2]){16                 p1++;17                 p2++;18             }19             if(p1 != str1.size() && p2 != str2.size())20                 graph[str1[p1]].push_back(str2[p2]);21             else{22                 if(p2 == str2.size() && str1.size() > str2.size())23                     return "";24             }25         }26         27         vector
           
             indegree(128,0);28         for(auto iter:graph){29             vector
            
              v = iter.second;30 for(char c:v)31 indegree[c]++;32 }33 34 string result = "";35 queue
             
               q;36 vector
              
                visited(128,false);37 for(int i = 0;i != 128;++i){38 if(allchar[i] && indegree[i] == 0){39 q.push(i);40 }41 }42 while(!q.empty()){43 char front = q.front();44 q.pop();45 result = result+front;46 visited[front] = true;47 if(graph.find(front) != graph.end()){48 for(int i = 0;i != graph[front].size();++i){49 if(visited[graph[front][i]]) return "";50 indegree[graph[front][i]]--;51 if(indegree[graph[front][i]] == 0)52 q.push(graph[front][i]);53 }54 }55 }56 for(int i = 0;i != 128;++i){57 if(indegree[i] != 0)58 return "";59 }60 return result;61 }62 };