# 4ms C++ solution using DFS

• ``````class Solution {
private:
bool dfs(string& result, vector<char> successors[], int visited[], char c) {
visited[c - 'a'] = 1;
for (char v : successors[c - 'a']) {
// visited[c - 'a'] == 0 represents c is never visited.
// visited[c - 'a'] == 1 represents c has been just visited in the same search so there is a cycle in the graph which makes the order invalid.
// visited[c - 'a'] == 2 represents c has been visited in a previous search.
if ((visited[v - 'a'] == 0 && !dfs(result, successors, visited, v)) || visited[v - 'a'] == 1)
return false;
}
visited[c - 'a'] = 2;
result = string(1, c) + result;
return true;
}
public:
string alienOrder(vector<string>& words) {
int n = (int)words.size();
vector<char> successors[26];
bool exists[26] = {0};
for (int i = 0; i != n; ++i) {
for (char c : words[i]) exists[c - 'a'] = true;
int len1 = (int)words[i].size(), len2 = i == n - 1 ? 0 : (int)words[i + 1].size(), j = 0;
while (j != len1 && j != len2 && words[i][j] == words[i + 1][j]) ++j;
if (j != len1 && j != len2) successors[words[i][j] - 'a'].push_back(words[i + 1][j]);
}
string result = "";
int visited[26] = {0};
for (char c = 'a'; c <= 'z'; ++c) {
if (exists[c - 'a'] && !visited[c - 'a'] && !dfs(result, successors, visited, c))
return "";
}
return result;
}
};
``````

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