Leetcode 269 Alien dictionary - study code

Leetcode269_AlienDictionary_studyCode.java

/*
Alien dictionary

7/21/2018 2:44 PM

Go over the blog and write down some notes as well. 

https://segmentfault.com/a/1190000003795463

拓扑排序
复杂度
时间 O(N) 空间 O(N)

思路
首先简单介绍一下拓扑排序，这是一个能够找出有向无环图顺序的一个方法

假设我们有3条边：A->C, B->C, C->D，先将每个节点的计数器初始化为0。然后我们对遍历边时，每遇到一个边，把目的节点的计数器
都加 1。然后，我们再遍历一遍，找出所有计数器值还是0的节点，这些节点就是有向无环图的“根”。然后我们从根开始广度优先搜索。
具体来说，搜索到某个节点时，将该节点加入结果中，然后所有被该节点指向的节点的计数器减1，在减1之后，如果某个被指向节点的计
数器变成 0 了，那这个被指向的节点就是该节点下轮搜索的子节点。在实现的角度来看，我们可以用一个队列，这样每次从队列头拿出来
一个加入结果中，同时把被这个节点指向的节点中计数器值减到0的节点也都加入队列尾中。需要注意的是，如果图是有环的，则计数器会
产生断层，即某个节点的计数器永远无法清零（有环意味着有的节点被多加了1，然而遍历的时候一次只减一个1，所以导致无法归零），
这样该节点也无法加入到结果中。所以我们只要判断这个结果的节点数和实际图中节点数相等，就代表无环，不相等，则代表有环。

对于这题来说，我们首先要初始化所有节点（即字母），一个是该字母指向的字母的集合（被指向的字母在字母表中处于较后的位置），一个
是该字母的计数器。然后我们根据字典开始建图，但是字典中并没有显示给出边的情况，如何根据字典建图呢？其实边都暗藏在相邻两个词之间，
比如abc和abd，我们比较两个词的每一位，直到第一个不一样的字母c和d，因为abd这个词在后面，所以d在字母表中应该是在c的后面。所以每
两个相邻的词都能蕴含一条边的信息。在建图的同时，实际上我们也可以计数了，对于每条边，将较后的字母的计数器加 1。计数时需要注意的是，
我们不能将同样一条边计数两次，所以要用一个集合来排除已经计数过的边。最后，我们开始拓扑排序，从计数器为 0 的字母开始广度优先搜索。
为了找到这些计数器为 0 的字母，我们还需要先遍历一遍所有的计数器。

最后，根据结果的字母个数和图中所有字母的个数，判断时候有环即可。无环直接返回结果。

注意
因为这题代码很冗长，面试的时候最好都把几个大步骤都写成子函数，先完成主函数，再实现各个子函数，比如初始化图，建图，加边，排序，
都可以分开

要先对字典里所有存在的字母初始化入度为0，否则之后建图可能会漏掉一些没有入度的字母

'a'+'b'+""和'a'+""+'b'是不一样的，前者先算数字和，后者则是字符串拼接

因为字典里有重复的边，所有要先判断，已经添加过的边不要重复添加

*/
public class Solution {
    public String alienOrder(String[] words) {
        // 节点构成的图
        Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>();
        // 节点的计数器
        Map<Character, Integer> indegree = new HashMap<Character, Integer>();
        // 结果存在这个里面
        StringBuilder order = new StringBuilder();
        // 初始化图和计数器
        initialize(words, graph, indegree);
        // 建图并计数
        buildGraphAndGetIndegree(words, graph, indegree);
        // 拓扑排序的最后一步，根据计数器值广度优先搜索
        topologicalSort(order, graph, indegree);
        // 如果大小相等说明无环
        return order.length() == indegree.size() ? order.toString() : "";
    }
    
    private void initialize(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        for(String word : words){
            for(int i = 0; i < word.length(); i++){
                char curr = word.charAt(i);
                // 对每个单词的每个字母初始化计数器和图节点
                if(graph.get(curr) == null){
                    graph.put(curr, new HashSet<Character>());
                }
                if(indegree.get(curr) == null){
                    indegree.put(curr, 0);
                }
            }
        }
    }
    
    private void buildGraphAndGetIndegree(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        Set<String> edges = new HashSet<String>();
        for(int i = 0; i < words.length - 1; i++){
        // 每两个相邻的词进行比较
            String word1 = words[i];
            String word2 = words[i + 1];
            for(int j = 0; j < word1.length() && j < word2.length(); j++){
                char from = word1.charAt(j);
                char to = word2.charAt(j);
                // 如果相同则继续，找到两个单词第一个不相同的字母
                if(from == to) continue;
                // 如果这两个字母构成的边还没有使用过，则
                if(!edges.contains(from+""+to)){
                    Set<Character> set = graph.get(from);
                    set.add(to);
                    // 将后面的字母加入前面字母的Set中
                    graph.put(from, set);
                    Integer toin = indegree.get(to);
                    toin++;
                    // 更新后面字母的计数器，+1
                    indegree.put(to, toin);
                    // 记录这条边已经处理过了
                    edges.add(from+""+to);
                    break;
                }
            }
        }
    }
    
    private void topologicalSort(StringBuilder order, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        // 广度优先搜索的队列
        Queue<Character> queue = new LinkedList<Character>();
        // 将有向图的根，即计数器为0的节点加入队列中
        for(Character key : indegree.keySet()){
            if(indegree.get(key) == 0){
                queue.offer(key);
            }
        }
        // 搜索
        while(!queue.isEmpty()){
            Character curr = queue.poll();
            // 将队头节点加入结果中
            order.append(curr);
            Set<Character> set = graph.get(curr);
            if(set != null){
                // 对所有该节点指向的节点，更新其计数器，-1
                for(Character c : set){
                    Integer val = indegree.get(c);
                    val--;
                    // 如果计数器归零，则加入队列中待处理
                    if(val == 0){
                        queue.offer(c);
                    }
                    indegree.put(c, val);
                }
            }
        }
    }
}