Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

思路，就是拓扑排序，从单词之间的关系来得到图的关系，然后用hashmap来建立图。注意分函数写程序，这样清晰，而且容易debug；注意indegree需要把每个node全部赋值为0；然后再进行+1；注意所有的char都是一个node，都是字母；这题有个特列：abc, ab, return  ""; 就是前面的相等，return "";

class Solution {
    public String alienOrder(String[] words) {
        HashMap<Character, HashSet<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> indegree = new HashMap<>();
        for(String word: words) {
            for(int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                graph.putIfAbsent(c, new HashSet<Character>());
            }
        }
        
        for(int i = 0; i < words.length - 1; i++) {
            String a = words[i];
            String b = words[i + 1];
            int minlen = Math.min(a.length(), b.length());
            for(int j = 0; j < minlen; j++) {
                if(a.charAt(j) != b.charAt(j)) {
                    graph.get(a.charAt(j)).add(b.charAt(j));
                    break;
                }
            }
            if(a.length() > b.length() && a.startsWith(b)) {
                return "";
            }
        }
        
        //build indegree;
        for(Character node: graph.keySet()) {
            indegree.putIfAbsent(node, 0);
            for(Character neighbor: graph.get(node)) {
                // node -> neighbor;
                indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1);
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        for(Character c: graph.keySet()) {
            if(indegree.get(c) != null && indegree.get(c) == 0) {
                queue.offer(c);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()) {
            Character ch = queue.poll();
            sb.append(ch);
            if(graph.get(ch) != null) {
                for(Character neighbor: graph.get(ch)) {
                    indegree.put(neighbor, indegree.get(neighbor) - 1);   
                    if(indegree.get(neighbor) == 0) {
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return sb.length() == graph.keySet().size() ? sb.toString() : "";
    }
}