269.Alien Dictionary

1-

首先，需要将其转换成为Graph。Map<Character, Set<Character>> map. 记录每个字符的后续字符
然后，需要统计每个字符的入度。
最后进行拓扑排序。
对于一个具有n个顶点e条弧的AOV网来说，将入度为0的顶点入栈的时间复杂度为O(n)，
之后，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，则整个算法的时间复杂度为O(n+e)。
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, 
asymptotically, O(E+N)

class Solution {
    public String alienOrder(String[] words) {
        //Key: char c, Val: characters that after char c.
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();

        //initialize indegree cnt
        for(String word : words){
            for(char c : word.toCharArray()){
                if(!indegree.containsKey(c))
                    indegree.put(c, 0);
            }
        }

        //compare word by word
        for(int i = 1 ; i < words.length; i++){
            char[] pre = words[i - 1].toCharArray();
            char[] cur = words[i].toCharArray();
            int length = Math.min(pre.length, cur.length);
            for(int j = 0; j < length; j++){
                //find different char
                if(pre[j] != cur[j]){
                    Set<Character> set= map.getOrDefault(pre[j], new HashSet<>());
                    if(!set.contains(cur[j])){
                        set.add(cur[j]);
                        map.put(pre[j], set);
                        indegree.put(cur[j], indegree.get(cur[j]) + 1);
                    }
                    break;
                }
            }
        }

        //Perform topological sort
        Deque<Character> queue = new ArrayDeque<>();
        for(char c : indegree.keySet()){
            if(indegree.get(c) == 0)
                queue.offer(c);
        }

        StringBuilder sb = new StringBuilder("");
        while(!queue.isEmpty()){
            char currentChar = queue.poll();
            sb.append(currentChar);
            indegree.remove(currentChar);
            if(map.containsKey(currentChar)){
                for(char next : map.get(currentChar)){
                    indegree.put(next, indegree.get(next) - 1);
                    if(indegree.get(next) <= 0){
                        queue.offer(next);
                    }
                }  
            }  
        }
        //If still remain edge not handled
        if(indegree.size() > 0)
            return "";
        else
            return sb.toString();
    }
}