# 3ms C++ solution, beats 100% of cpp submission

• My algorithm is typical: 1. construct the graph, and 2. topological sort.

For constructing the graph, I use a vertical approach by comparing letters column-by-column. Many top answers constructed the graph by comparing letters of 2 consecutive rows. I checked both the algorithms but the run time was the same so the reason which makes my code faster than others may lay on the topological sort.

For topological sort, I use BFS and detect the feasibility by comparing the length of the result with the number of available characters. The traversal is done by checking the nodes whose in-edges are 0 repeatedly. This should be faster than using hash directly.

``````class Solution {
public:
string alienOrder(vector<string>& words) {
bool chars[26] = {false};
bool order[26][26] = {false};
findOrder(words, 0, words.size(), 0, order, chars);

int in_edges[26] = {0};
int num_chars = 0;
for (int i = 0; i < 26; ++i) {
if (chars[i]) {
for (int j = 0; j < 26; ++j) {
if (order[i][j])
in_edges[j]++;
}
++num_chars;
}
}
queue<int> q;
for (int i = 0; i < 26; ++i) {
if (chars[i] && in_edges[i] == 0)
q.emplace(i);
}

string result;
while (!q.empty()) {
int cur = q.front(); q.pop();
result += cur + 'a';
for (int i = 0; i < 26; ++i) {
if (order[cur][i]) {
if (--in_edges[i] == 0)
q.emplace(i);
}
}
}

return result.length() == num_chars ? result : "";
}

void findOrder(const vector<string>& words, int begin, int end, int pos, bool order[][26], bool chars[]) {
if (pos < words[begin].length())
chars[words[begin][pos] - 'a'] = true;
for (int i = begin + 1; i < end; ++i) {
if (pos < words[i - 1].length() && pos < words[i].length() && words[i-1][pos] != words[i][pos]) {
order[words[i-1][pos] - 'a'][words[i][pos] - 'a'] = true;
chars[words[i-1][pos] - 'a'] = true;
chars[words[i][pos] - 'a'] = true;
}
}

int i = begin;
while (i < end) {
while (i < end && pos >= words[i].length()) ++i;
if (i == end)
break;
int prev = i;
++i;
while (i < end && pos < words[i].length() && words[i-1][pos] == words[i][pos])   ++i;
findOrder(words, prev, i, pos + 1, order, chars);
}
}
};
``````

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