摘要：拓?fù)渑判驈?fù)雜度時(shí)間空間思路首先簡單介紹一下拓?fù)渑判颍@是一個(gè)能夠找出有向無環(huán)圖順序的一個(gè)方法假設(shè)我們有條邊，先將每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后，我們開始拓?fù)渑判?，從?jì)數(shù)器為的字母開始廣度優(yōu)先搜索。

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.

對(duì)于這題來說，我們首先要初始化所有節(jié)點(diǎn)（即字母），一個(gè)是該字母指向的字母的集合（被指向的字母在字母表中處于較后的位置），一個(gè)是該字母的計(jì)數(shù)器。然后我們根據(jù)字典開始建圖，但是字典中并沒有顯示給出邊的情況，如何根據(jù)字典建圖呢？其實(shí)邊都暗藏在相鄰兩個(gè)詞之間，比如abc和abd，我們比較兩個(gè)詞的每一位，直到第一個(gè)不一樣的字母c和d，因?yàn)?b>abd這個(gè)詞在后面，所以d在字母表中應(yīng)該是在c的后面。所以每兩個(gè)相鄰的詞都能蘊(yùn)含一條邊的信息。在建圖的同時(shí)，實(shí)際上我們也可以計(jì)數(shù)了，對(duì)于每條邊，將較后的字母的計(jì)數(shù)器加1。計(jì)數(shù)時(shí)需要注意的是，我們不能將同樣一條邊計(jì)數(shù)兩次，所以要用一個(gè)集合來排除已經(jīng)計(jì)數(shù)過的邊。最后，我們開始拓?fù)渑判颍瑥挠?jì)數(shù)器為0的字母開始廣度優(yōu)先搜索。為了找到這些計(jì)數(shù)器為0的字母，我們還需要先遍歷一遍所有的計(jì)數(shù)器。

最后，根據(jù)結(jié)果的字母個(gè)數(shù)和圖中所有字母的個(gè)數(shù)，判斷時(shí)候有環(huán)即可。無環(huán)直接返回結(jié)果。

因?yàn)檫@題代碼很冗長，面試的時(shí)候最好都把幾個(gè)大步驟都寫成子函數(shù)，先完成主函數(shù)，再實(shí)現(xiàn)各個(gè)子函數(shù)，比如初始化圖，建圖，加邊，排序，都可以分開

要先對(duì)字典里所有存在的字母初始化入度為0，否則之后建圖可能會(huì)漏掉一些沒有入度的字母

"a"+"b"+""和"a"+""+"b"是不一樣的，前者先算數(shù)字和，后者則是字符串拼接

因?yàn)樽值淅镉兄貜?fù)的邊，所有要先判斷，已經(jīng)添加過的邊不要重復(fù)添加

    public class Solution {
        public String alienOrder(String[] words) {
            // 節(jié)點(diǎn)構(gòu)成的圖
            Map> graph = new HashMap>();
            // 節(jié)點(diǎn)的計(jì)數(shù)器
            Map indegree = new HashMap();
            // 結(jié)果存在這個(gè)里面
            StringBuilder order = new StringBuilder();
            // 初始化圖和計(jì)數(shù)器
            initialize(words, graph, indegree);
            // 建圖并計(jì)數(shù)
            buildGraphAndGetIndegree(words, graph, indegree);
            // 拓?fù)渑判虻淖詈笠徊?，根?jù)計(jì)數(shù)器值廣度優(yōu)先搜索
            topologicalSort(order, graph, indegree);
            // 如果大小相等說明無環(huán)
            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);
                    // 對(duì)每個(gè)單詞的每個(gè)字母初始化計(jì)數(shù)器和圖節(jié)點(diǎn)
                    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++){
            // 每兩個(gè)相鄰的詞進(jìn)行比較
                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);
                    // 如果相同則繼續(xù)，找到兩個(gè)單詞第一個(gè)不相同的字母
                    if(from == to) continue;
                    // 如果這兩個(gè)字母構(gòu)成的邊還沒有使用過，則
                    if(!edges.contains(from+""+to)){
                        Set set = graph.get(from);
                        set.add(to);
                        // 將后面的字母加入前面字母的Set中
                        graph.put(from, set);
                        Integer toin = indegree.get(to);
                        toin++;
                        // 更新后面字母的計(jì)數(shù)器，+1
                        indegree.put(to, toin);
                        // 記錄這條邊已經(jīng)處理過了
                        edges.add(from+""+to);
                        break;
                    }
                }
            }
        }
        
        private void topologicalSort(StringBuilder order, Map> graph, Map indegree){
            // 廣度優(yōu)先搜索的隊(duì)列
            Queue queue = new LinkedList();
            // 將有向圖的根，即計(jì)數(shù)器為0的節(jié)點(diǎn)加入隊(duì)列中
            for(Character key : indegree.keySet()){
                if(indegree.get(key) == 0){
                    queue.offer(key);
                }
            }
            // 搜索
            while(!queue.isEmpty()){
                Character curr = queue.poll();
                // 將隊(duì)頭節(jié)點(diǎn)加入結(jié)果中
                order.append(curr);
                Set set = graph.get(curr);
                if(set != null){
                    // 對(duì)所有該節(jié)點(diǎn)指向的節(jié)點(diǎn)，更新其計(jì)數(shù)器，-1
                    for(Character c : set){
                        Integer val = indegree.get(c);
                        val--;
                        // 如果計(jì)數(shù)器歸零，則加入隊(duì)列中待處理
                        if(val == 0){
                            queue.offer(c);
                        }
                        indegree.put(c, val);
                    }
                }
            }
        }
    }

新建一個(gè)AlienChar數(shù)據(jù)結(jié)構(gòu)重寫，只用一個(gè)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 "";
        }
        // 在建好的圖中根據(jù)拓?fù)渑判虮闅v
        String order = findOrder(graph);
        return order.length() == graph.size() ? order : "";
    }
    
    private boolean buildGraph(String[] words, Map graph){
        HashSet visited = new HashSet();
        // 初始化圖，每個(gè)字母都初始化入度為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;
            // 找到相鄰兩個(gè)單詞第一個(gè)不一樣的字母
            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;
                }
            }
            // 如果有環(huán)，則建圖失敗
            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 ""
}