# Problem breakdown 9ms java solution with some explaination

• The problem can be treated as a topology sort problem, since in topology sort, the result is the list that from root to leaf in order.
There are several components in topology sort model.

1. we need to find all the vertices
2. we need to find all the edges
3. build the directed graph
4. build the order

There are several special cases here.

1. if there is cycle, for example, `["a", "b", "a"]` . There is not valid order, should return "".
2. if the next word is the prefix of the current word `["ab", "a" ]`, it's not valid either
3. if the order can't be found, and it's still valid dictionary, for example `["ab", "ab"]`, both`"ab", "ba"` are valid results.
``````public String alienOrder(String[] words) {
int n = words.length;
if(n == 0) return "";
List<char[]> edges = new ArrayList();
// get all chars appeared
Set<Character> set = new HashSet<Character>();
for(int i = 0; i < n ; i++){
for(char c : words[i].toCharArray()){
if(!set.contains(c)){
}
}
}

// build edge
for(int i = 0; i < n -1 ; i++){
if(words[i].equals(words[i+1])) continue;
char[] edge = getEdge(words[i], words[i+1]);
// special case #2
if(edge[0] == '*') return "";
if(edge[0] == '\u0000') continue;
}

List<Integer>[] graph = new ArrayList[26];
int[] indegrees = new int[26];

// build graph
for(char[] edge : edges){
if(graph[edge[0] -'a'] == null){
graph[edge[0] -'a'] = new ArrayList();
}
indegrees[edge[1] -'a']++;
}

// topology sort
for(char i : set){
if(indegrees[i-'a'] == 0){
q.offer(i-'a');
}
}
char[] orders = new char[set.size()];
int pos = 0;
while(!q.isEmpty()){
Integer cur = q.poll();
orders[pos] = (char)(cur + 'a');
pos++;

if(graph[cur] != null){
for(Integer nb : graph[cur]){
indegrees[nb]--;
if(indegrees[nb] == 0){
q.offer(nb);
}
}
}
}
// check cycle
if(edges.size() != 0 && pos != set.size()) return "";
StringBuilder rt = new StringBuilder();
for(char c : orders){
if(c == '\u0000') continue;
rt.append(c);
}
return rt.toString();
}

char[] getEdge(String s, String l){
int len1 = s.length();
int len2 = l.length();
char[] edge = new char[2];
for(int i = 0; i< len1 && i < len2;i++){
if(s.charAt(i) == l.charAt(i))
continue;
else
{
edge[0] = s.charAt(i);
edge[1] = l.charAt(i);
return edge;
}
}
if(len1 > len2){
edge[0] = '*';
}
return edge;
}
``````

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