A C++ soution with explanations, build graph + topological sort

• ``````class Solution{
private:
int inline getIndex(char c){
return (int)(c - 'a');
}
public:
string alienOrder(vector<string>& words) {
string result;
if(words.size() <= 1){
return result;
}

unordered_set<char> zeroInDegreeChars;
// First, we assume there is no relationship between chars, so every char has 0 indegree.
vector<unordered_set<char>> charIndgrees(26, unordered_set<char>());
for(auto w : words){
for(auto c : w){
zeroInDegreeChars.insert(c);
}
}

// Build indgree graph.
// For example, if we met "ad" then "ab", we know 'd' < 'b'
// To record this, we add d to b's precedent char set, which means d points to b.
// Meanwhile, we remove b from the zeroInDegreeChars set, since now it has a precedence.
for(size_t i = 1; i < words.size(); i++){
string w1 = words[i-1], w2 = words[i];
size_t len = min(w1.size(), w2.size());
for(size_t j = 0; j < len; j++){
if(w1[j] != w2[j]){
char c1 = w1[j], c2 = w2[j];
zeroInDegreeChars.erase(c2);
charIndgrees[getIndex(c2)].insert(c1);
}
}
}

// Do topology sort, every time, pick up a 0 indegree char.
while(!zeroInDegreeChars.empty()){
char c = *(zeroInDegreeChars.begin());
result += c;
zeroInDegreeChars.erase(c);
// Remove c from the precedence sets of other chars.
for(size_t i = 0; i < charIndgrees.size(); i++){
auto indgreeSet = charIndgrees[i];
if(!indgreeSet.empty()){
if(indgreeSet.find(c) != indgreeSet.end()){
indgreeSet.erase(c);
// If c is the only precedence of current char,
// we can add current char to zeroInDegreeChars now.
if(indgreeSet.empty()){
zeroInDegreeChars.insert((char)(i + 'a'));
}
}
}
}
}

return result;
}
};
``````

Tested with a few cases but haven't tested with the OJ system.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.