# AC Java solution (Topsort + BFS) simple and easy to understand

• public class Solution {

``````public String alienOrder(String[] words) {
Map<Character, HashSet<Character>> hashmap = new HashMap();
int[] pre = new int[26];

for(int i = 0; i < words.length; i++){
//put every letter into map
char[] chs = words[i].toCharArray();
for(char c : chs)
if(!hashmap.containsKey(c)) hashmap.put(c, new HashSet<Character>());
if(i == 0)  continue;

//from the second element, compare itself to its previous element and find the order of letters
int p = 0;
int len = Math.min(words[i-1].length(), words[i].length());
while(p < len && words[i-1].charAt(p) == words[i].charAt(p))    p++;
if(p == len)    continue;

char ch1 = words[i-1].charAt(p), ch2 = words[i].charAt(p);
pre[ch2 - 'a']++;
}
}

//take in those characters that no previous character needed
for(int i = 0; i < pre.length; i++){
char c = (char)('a'+i);
if(pre[i] == 0 && hashmap.containsKey(c))     queue.offer(c);
}

//consume the character after all previous characters showed up
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()){
char cur = queue.poll();
sb.append(cur);
for(Object ob : hashmap.get(cur)){
char ch = (char)ob;
pre[ch -'a']--;
if(pre[ch-'a'] == 0){
}
}
}
//find those characters that will never be used (invalid order e.g. cycle)
for(int i = 0; i < 26; i++){
if(pre[i] > 0)
return "";
}
return sb.toString();
}
``````

}

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