# 9 ms Java solution based on DFS with detailed comments

• ``````class Solution {
public String alienOrder(String[] words) {
// Build a graph in which an edge from A to B indicates that A appears before B in the alphabet
Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>();
for(String word : words) {
for(Character node : word.toCharArray()) {
if(!graph.containsKey(node)) {
graph.put(node, new HashSet<Character>());
}
}
}
for(int i = 0; i < words.length - 1; i++) {
String w1 = words[i];
String w2 = words[i + 1];
int minLength = Math.min(w1.length(), w2.length());
int j = 0;
while(j < minLength && w1.charAt(j) == w2.charAt(j)) {
j++;
}
if(j < minLength) {
}
}
// Perform a topological sorting based on DFS.
StringBuilder sb = new StringBuilder();
Set<Character> visited = new HashSet<Character>();
Set<Character> ancestors = new HashSet<Character>();
for(char node : graph.keySet()) {
if(!visited.contains(node)) {
if(!DFS(node, graph, visited, ancestors, sb)) {
return "";
};
}
}
return sb.toString();
}

private Boolean DFS(char root, Map<Character, Set<Character>> graph, Set<Character> visited, Set<Character> ancestors, StringBuilder sb)     {
if(ancestors.contains(root)) {
// We found a cycle in the graph. It is impossible to derive the order of letters.
return false;
}
for(char child : graph.get(root)) {
if(!visited.contains(child)) {
if(!DFS(child, graph, visited, ancestors, sb)) {
return false;
}
}
}
ancestors.remove(root);