# Simple idea based on DFS [4ms] in C++

• My idea is very straight-forward.
First use the dictionary vector to construct a graph using adjacency matrix and the diagonal elements is used to store whether the alphabet appears in the dictionary or not.
Then perform DFS to find the sequence for each potential root node.
If there is a cycle or unvisited node, return "".

``````class Solution {
public:
void findEdges(string &word1, string &word2, bool graph[][26]){
// construct the graph
int tmpLen = min(word1.length(), word2.length());
for (int i = 0; i < tmpLen; i++){
if (word1[i] != word2[i]){
graph[word1[i]-'a'][word2[i]-'a'] = true;
break;
}
}
}
bool dfs(string &res, vector<bool> &tmpMark, bool graph[][26], int root){
// perform topological sort, return whether there is a cycle
if (tmpMark[root]){
res = "";
return true;
}
tmpMark[root] = true;
for (int i = 0;i < 26; i++){
if (i != root && graph[root][i]){
if (dfs(res, tmpMark, graph, i)){
return true;
}
}
}
graph[root][root] = false;
tmpMark[root] = false;
char tmp = root + 'a';
res = tmp + res;
return false;
}

string alienOrder(vector<string>& words) {
string res;
if (words.size() == 0){
return res;
}
if (words.size() == 1) return words[0];
bool graph[26][26] = {false};
for (char c : words[0]){
graph[c-'a'][c -'a'] = true;
}
for (int i = 1; i < words.size(); i++){
for (char c : words[i]){
graph[c -'a'] [c -'a'] = true;
}
findEdges(words[i-1], words[i], graph);
}

for (int i = 0; i < 26; i++){
// find a root node;
bool rootNode = graph[i][i];
if (graph[i][i]){
for (int j = 0; j < 26; j++){
if ( j != i && graph[j][i]){
rootNode = false;
break;
}
}
}
if (rootNode){
string tmpRes = "";
vector<bool> tmpMark(26, false);
if (dfs(tmpRes, tmpMark, graph, i))
return "";
else
res += tmpRes;
}
}

// if there is still unvisited node, return "";
for (int i = 0; i < 26; i++){
if (graph[i][i]) return "";
}
return res;
}
};``````

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