# My Concise JAVA solution based on Topological Sorting

• This problem is actually similar as Course Schedule II. The basic idea to solve this problem:

``````1. Convert characters to a graph: Adjacency lists
2. Topological sorting: keep adding elements whose in-degree is 0
``````

While figuring out the solution, it helped me to understand topological sorting entirely.

Topological sorting: The classic linear algorithm to solve dependency problems, e.g. course schedule.

In-degree: The amount of dependencies of the element E, which means the amount of E's predecessors. We have to fulfill E's predecessors before executing E, when E's in-degree = 0.

Time complexity = O(n + m) - n represents all vertices, m represents all edges

JAVA Code:

``````public String alienOrder(String[] words) {
List<Point> pairs = new LinkedList<Point>(); // Adjacency list: pair = (node, node's predecessor)
Set<Character>chs = new HashSet<Character>();// All distinct characters

// 1. Convert characters to a graph: Adjacency lists
for (int i = 0; i < words.length; i++) {
String word = words[i];
boolean alreadySet = false;// Only set one pair where the characters at the same position differs in two neighbor rows. e.g. "wrtk" < "wrfp"=> 't' < 'f'
for (int j = 0; j < words[i].length(); j++) {
if (!alreadySet && i > 0 && j < words[i-1].length() && words[i].charAt(j) != words[i-1].charAt(j)) {// Set dependency of two characters by comparing two neighbor rows.
}
}
}

// 2. Topological sorting: keep adding elements whose in-degree is 0
String res = "";
int indegree[] = new int[256];
Arrays.fill(indegree, Integer.MIN_VALUE);

for (Character ch : chs) indegree[ch] = 0;// Initialize in-degree of the distinct characters in the words list
for (int i = 0; i < pairs.size(); i++)// Increase in-degree according to the dependency of pairs list
indegree[pairs.get(i).x]++;

for (int i = 0; i < 256; i++) {
if (indegree[i] == 0) {// Add the character whose in-degree = 0, which means it doesn't have any predecessor
res += (char) i;
queue.offer((char) i);
}
}

while (!queue.isEmpty()) {
Character predecessor = queue.poll(); // Dequeue the character whose in-degree = 0 from queue

for (int i = 0; i < pairs.size(); i++) {
if (pairs.get(i).y == predecessor) {// Update in-degree: decrease 1 to the successors of the character whose in-degree = 0
indegree[pairs.get(i).x]--;
if (indegree[pairs.get(i).x] == 0) {// If in-degree = 0, add the character to the queue, and append it to the result string
res += (char) pairs.get(i).x;
queue.offer((char) pairs.get(i).x);
}
}
}
}
return res.length() == chs.size() ? res : "";// NOTE: res.length should equal the size of distinct characters, otherwise a cycle must exist
}
``````

• ``````    Great solution, and it pass the test cases.
But only one place I don't quite understand,
when you build the graph:
if (words[i].charAt(j) != words[i-1].charAt(j)) {
I think this statement is wrong, for example in English:
ba>ac in lexicographically  but you cannot say that
a>c(word[0].charAt(1),word[1].charAt(1) in lexicographically.
``````

• This post is deleted!

• Thanks for your comment, yidong! In the case ba>ac, only b>a will be set, then the locker 'alreadySet'=true, which prevents the cases after b.

• Updated the corresponding part, hope it's clearer now ;)

• This post is deleted!

• Runs in 5ms

``````public class Solution {
public String alienOrder(String[] words) {
if(words==null || words.length==0) return "";
boolean[][] graph=new boolean[26][26];
//indegree array used to record the indegree of character and also whether the character exists in alien dictionary
int[] indegree=new int[26];
/*indegree[i] = -1 means the character doesn't exist in alien dictionary
0 means the character's indegree is 0
n means the character's indegree is n
*/
Arrays.fill(indegree, -1);
char[] pre=words[0].toCharArray(), current=null;
/*compare two consecutive words in the alien dictionary, find the first two different character and draw a line from the pre-word's character to current-word's character
(suppose we are drawing a graph from character a to character b if a comes before b)
*/
for(char x:pre) indegree[x-'a']=0;
for(int i=1;i<words.length;i++){
current=words[i].toCharArray();
for(char x: current) indegree[x-'a']=0;
int index=0;
while(index<pre.length&&index<current.length&&pre[index]==current[index]) index++;
/* handle the cases that one of the word is the prefix of another word
For example: "wrt" follows by "wrtff" or
"wrtff" follows by "wrt"
the first case should be correct, the second one is assumed incorrect
*/
if(index==current.length){
if(pre.length==current.length) continue;
else return "";
}
if(index==pre.length) continue;
graph[pre[index]-'a'][current[index]-'a']=true;
pre=current;
}
/* alphabetCount record how many characters that exist in alien dictionary, We are gonna use this variable to check whether the graph we build has cycle inside
*/
int alphabetCount=0;
for(int a: indegree){
if(a==0) alphabetCount++;
}
//caculate each character's indegree
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(graph[i][j]){
indegree[j]++;
}
}
}
for(int i=0;i<26;i++){
if(indegree[i]==0) queue.offer(i);
}
StringBuilder order=new StringBuilder();
while(!queue.isEmpty()){
int tmp=queue.poll();
order.append((char)('a'+tmp));
for(int next=0;next<26;next++){
if(graph[tmp][next]){
if(--indegree[next]==0) queue.offer(next);
graph[tmp][next]=false;
}
}
}
return order.length()==alphabetCount?order.toString():"";
}
}
``````

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