Also this one in DIY: Alien Dictionary - Decode the Coding Interview in Java: Real-World Examples
class Solution {
public static String alienOrder(String[] words) {
Map<Character, List<Character>> adjList = new HashMap<Character, List<Character>>();
Map<Character, Integer> counts = new HashMap<>();
for(String word: words) {
for(char c: word.toCharArray()) {
counts.put(c,0);
adjList.put(c, new ArrayList<Character>());
}
}
for(int i=0;i<words.length-1;i++) {
String word1 = words[i];
String word2 = words[i+1];
if(word1.length()>word2.length() && word1.startsWith(word2)) {
return "";
}
for(int j=0;i<Math.min(word1.length(),word2.length());j++) {
if(word1.charAt(j) != word2.charAt(j)) {
adjList.get(word1.charAt(j)).add(word2.charAt(j));
counts.put(word2.charAt(j),counts.get(word2.charAt(j))+1);
break;
}
}
}
StringBuilder result = new StringBuilder();
Queue<Character> queue = new LinkedList<>();
for(Character c: counts.keySet()) {
if(counts.get(c).equals(0)) {
queue.add(c);
}
}
while(!queue.isEmpty()) {
Character c = queue.remove();
result.append(c);
for(Character next: adjList.get(c)) {
counts.put(next,counts.get(next)-1);
if(counts.get(next).equals(0)) {
queue.add(next);
}
}
}
if(result.length()<counts.size()) {
return "";
}
return result.toString();
}
}