摘要：拓撲排序復雜度時間空間思路首先簡單介紹一下拓撲排序，這是一個能夠找出有向無環圖順序的一個方法假設我們有條邊，先將每個節點的計數器初始化為。最后，我們開始拓撲排序，從計數器為的字母開始廣度優先搜索。

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: You may assume all letters are in lowercase. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.

時間 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> graph = new HashMap>();
            // 節點的計數器
            Map indegree = new HashMap();
            // 結果存在這個里面
            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> graph, Map 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());
                    }
                    if(indegree.get(curr) == null){
                        indegree.put(curr, 0);
                    }
                }
            }
        }
        
        private void buildGraphAndGetIndegree(String[] words, Map> graph, Map indegree){
            Set edges = new HashSet();
            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 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> graph, Map indegree){
            // 廣度優先搜索的隊列
            Queue queue = new LinkedList();
            // 將有向圖的根，即計數器為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 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);
                    }
                }
            }
        }
    }

新建一個AlienChar數據結構重寫，只用一個Map作為Graph自身

public class Solution {
    public String alienOrder(String[] words) {
        Map graph = new HashMap();
        // 如果建圖失敗，比如有a->b和b->a這樣的邊，就返回false
        boolean isBuildSucceed = buildGraph(words, graph);
        if(!isBuildSucceed){
            return "";
        }
        // 在建好的圖中根據拓撲排序遍歷
        String order = findOrder(graph);
        return order.length() == graph.size() ? order : "";
    }
    
    private boolean buildGraph(String[] words, Map graph){
        HashSet visited = new HashSet();
        // 初始化圖，每個字母都初始化入度為0
        initializeGraph(words, graph);
        for(int wordIdx = 0; wordIdx < words.length - 1; wordIdx++){
            String before = words[wordIdx];
            String after = words[wordIdx + 1];
            Character prev = null, next = null;
            // 找到相鄰兩個單詞第一個不一樣的字母
            for(int letterIdx = 0; letterIdx < before.length() && letterIdx < after.length(); letterIdx++){
                if(before.charAt(letterIdx) != after.charAt(letterIdx)){
                    prev = before.charAt(letterIdx);
                    next = after.charAt(letterIdx);
                    break;
                }
            }
            // 如果有環，則建圖失敗
            if(prev != null && visited.contains(next + "" + prev)){
                return false;
            }
            // 如果這條邊沒有添加過，則在圖中加入這條邊
            if(prev != null && !visited.contains(prev + "" + next)){
                addEdge(prev, next, graph);
                visited.add(prev + "" + next);
            }
        }
        return true;
    }
    
    private void initializeGraph(String[] words, Map graph){
        for(String word : words){
            for(int idx = 0; idx < word.length(); idx++){
                if(!graph.containsKey(word.charAt(idx))){
                    graph.put(word.charAt(idx), new AlienChar(word.charAt(idx)));
                }
            }
        }
    }
    
    private void addEdge(char prev, char next, Map graph){
        AlienChar prevAlienChar = graph.get(prev);
        AlienChar nextAlienChar = graph.get(next);
        nextAlienChar.indegree += 1;
        prevAlienChar.later.add(nextAlienChar);
        graph.put(prev, prevAlienChar);
        graph.put(next, nextAlienChar);
    }
    
    private String findOrder(Map graph){
        StringBuilder order = new StringBuilder();
        Queue queue = new LinkedList();
        for(Character c : graph.keySet()){
            if(graph.get(c).indegree == 0){
                queue.offer(graph.get(c));
            }
        }
        while(!queue.isEmpty()){
            AlienChar curr = queue.poll();
            order.append(curr.val);
            for(AlienChar next : curr.later){
                if(--next.indegree == 0){
                    queue.offer(next);
                }
            }
        }
        return order.toString();
    }
}

class AlienChar {
    char val;
    ArrayList later;
    int indegree;
    public AlienChar(char c){
        this.val = c;
        this.later = new ArrayList();
        this.indegree = 0;
    }
}

2018/10

func buildGraphAndIndegree(words []string) (map[byte][]byte, map[byte]int) {
    graph := make(map[byte][]byte)
    indegree := make(map[byte]int)
    for i := 1; i < len(words); i++ {
        prev := words[i-1]
        curr := words[i]
        for idx := range prev {
            if idx >= len(prev) {
                break
            }
            prevChar := prev[idx]
            if _, ok := indegree[prevChar]; !ok {
                indegree[prevChar] = 0
            }
            if idx >= len(curr) {
                break
            }
            currChar := curr[idx]
            if prevChar == currChar {
                continue
            }
            targets := graph[prevChar]
            found := false
            for _, el := range targets {
                if el == currChar {
                    found = true
                }
            }
            if !found {
                graph[prevChar] = append(targets, currChar)
                indegree[currChar]++
            }
        }
    }
    return graph, indegree
}

func alienOrder(words []string) string {
    graph, indegree := buildGraphAndIndegree(words)
    // find the first batch of roots for topological sort
    var roots []byte
    sb := strings.Builder{}
    for key, value := range indegree {
        if value == 0 {
            roots = append(roots, key)
            sb.WriteByte(key)
        }
    }
    // keep sorting
    for len(roots) != 0 {
        newRoots := []byte{}
        for _, root := range roots {
            targets := graph[root]
            for _, target := range targets {
                if indegree[target] > 0 {
                    indegree[target]--
                }
                if indegree[target] == 0 {
                    newRoots = append(newRoots, target)
                }
            }
        }
        for _, root := range newRoots {
            sb.WriteByte(root)
        }
        roots = newRoots
    }
    if sb.Len() == len(indegree) {
        return sb.String()
    }
    return ""
}