# My 6ms C++ Solution

• ``````class Solution {
public:
string alienOrder(vector<string>& words) {
// handle special cases
if(words.size() == 0) return "";
bool valid = false;
vector<bool> chars(26, false);
for(string word: words) {
for(char c: word) {
chars[c-'a'] = true;
}
}
if(words.size() == 1) valid = true;
if(words.size() == 2 && words[0] == words[1]) valid = true;

// construct a directed graph and a reversed graph
vector<unordered_set<char>> graph(26);
vector<unordered_set<char>> r_graph(26);

for(int i = 0; i < words.size() - 1; i++) {
string cur = words[i];
string next = words[i+1];
// by comparing the adjacent 2, we can derive some of the characters' orders
int k = 0;
// set all the seen chars to be seen;
while(k<cur.length() && k<next.length() && cur[k] == next[k]) k++;
if(k<cur.length() && k<next.length()) {
valid = true;
// construct directed graph and reversed directed graph;
graph[cur[k]-'a'].insert(next[k]);
r_graph[next[k]-'a'].insert(cur[k]);
}
}

if(!valid) return {};

bool has_node = false;
bool remove1 = false;
string res = "";
// topological sort the graph (with cycle):
while(true) {
has_node = false;
remove1 = false;
for(int i = 0; i < 26; i++) {
if(chars[i]) {
has_node = true;
// check if the current node with 0 in-degree
if(r_graph[i].empty()) {
remove1 = true;
res.push_back('a'+i);
// remove all the edges connected to the current node;
for(char c : graph[i]) {
r_graph[c-'a'].erase('a'+i);
}
graph[i] = {};
// mark current node as removed;
chars[i] = false;
}
}
}
// then there is cycle
if(has_node && !remove1) return {};
// do until there is no node left in the graph;
if(!remove1) break;
}
return res;
}
};
``````

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