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:
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. class Solution { public: string alienOrder(vector<string>& words) { if(words.empty()) return "" ; if(words.size() == 1) { sort(words[0].begin() , words[0].end()) ; return words[0] ; } unordered_map<char , int> indegree ; unordered_set<char> visited ; unordered_map<char , unordered_set<char>> edges ; unordered_map<int , set<char>> indegree_nodes ; string res ; for(int i = 0 ; i < words.size() - 1 ; ++i) { string word_1 = words[i] , word_2 = words[i + 1] ; for(int j = 0 ; j < word_1.size() ; ++j) visited.insert(word_1[j]) ; for(int j = 0 ; j < word_2.size() ; ++j) visited.insert(word_2[j]) ; int pos = 0 ; for(; pos < min(word_1.size() , word_2.size()) ; ++pos) { if(word_1[pos] != word_2[pos]) break ; } if(pos < min(word_1.size() , word_2.size())) { if(edges.count(word_1[pos]) && edges[word_1[pos]].count(word_2[pos])) continue ; if(!indegree.count(word_1[pos])) { indegree[word_1[pos]] = 0 ; indegree_nodes[0].insert(word_1[pos]) ; } edges[word_1[pos]].insert(word_2[pos]) ; if(indegree.count(word_2[pos])) indegree_nodes[indegree[word_2[pos]]].erase(word_2[pos]) ; if(indegree_nodes[indegree[word_2[pos]]].empty()) indegree_nodes.erase(indegree[word_2[pos]]) ; indegree[word_2[pos]]++ ; indegree_nodes[indegree[word_2[pos]]].insert(word_2[pos]) ; } } while(1) { if(indegree_nodes.empty()) { if(!visited.empty()) { string tmp = "" ; for(auto c : visited) tmp += string(1 , c) ; sort(tmp.begin() , tmp.end()) ; return res + tmp ; } return res ; } if(!indegree_nodes.count(0)) return "" ; cout<<"in"<<endl; char node = *indegree_nodes[0].begin() ; cout<<"node:"<<node<<endl; res += string(1 , node) ; indegree_nodes[0].erase(node) ; visited.erase(node) ; if(indegree_nodes[0].empty()) indegree_nodes.erase(0) ; for(auto n : edges[node]) { indegree_nodes[indegree[n]].erase(n) ; if(indegree_nodes[indegree[n]].empty()) indegree_nodes.erase(indegree[n]) ; indegree[n]-- ; indegree_nodes[indegree[n]].insert(n) ; } edges.erase(node) ; } } };
