[leetcode/lintcode 題解] 國内大廠面試真題詳解：外星人字典

描述

有一種新的使用拉丁字母的外來語言。但是，你不知道字母之間的順序。你會從詞典中收到一個非空的單詞清單，其中的單詞在這種新語言的規則下按字典順序排序。請推導出這種語言的字母順序。

1. 你可以假設所有的字母都是小寫。
2. 如果a是b的字首且b出現在a之前，那麼這個順序是無效的。
3. 如果順序是無效的，則傳回空字元串。
4. 這裡可能有多個有效的字母順序，傳回以正常字典順序看來最小的。

線上評測位址：

領扣題庫官網

樣例1
輸入：["wrt","wrf","er","ett","rftt"]
輸出："wertf"
解釋：
從 "wrt"和"wrf" ,我們可以得到 't'<'f'
從 "wrt"和"er" ,我們可以得到'w'<'e'
從 "er"和"ett" ,我們可以得到 get 'r'<'t'
從 "ett"和"rftt" ,我們可以得到 'e'<'r'
是以傳回 "wertf"           

樣例2
輸入：["z","x"]
輸出："zx"
解釋：
從 "z" 和 "x"，我們可以得到 'z' < 'x'
是以傳回"zx"           

解題思路

使用拓撲排序算法。 這個版本的實作當中，無需假設所有字母為小寫字母。

源代碼

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = constructGraph(words);
        if (graph == null) {
            return "";
        }
        return topologicalSorting(graph);
    }
    
        
    private Map<Character, Set<Character>> constructGraph(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        
        // create nodes
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                if (!graph.containsKey(c)) {
                    graph.put(c, new HashSet<Character>());
                }
            }
        }
        
        // create edges
        for (int i = 0; i < words.length - 1; i++) {
            int index = 0;
            while (index < words[i].length() && index < words[i + 1].length()) {
                if (words[i].charAt(index) != words[i + 1].charAt(index)) {
                    graph.get(words[i].charAt(index)).add(words[i + 1].charAt(index));
                    break;
                }
                index++;
            }
            if (index == Math.min(words[i].length(), words[i + 1].length())) {
                if (words[i].length() > words[i + 1].length()) {
                    return null;
                }
            }
        }

        return graph;
    }
    
    private Map<Character, Integer> getIndegree(Map<Character, Set<Character>> graph) {
        Map<Character, Integer> indegree = new HashMap<>();
        for (Character u : graph.keySet()) {
            indegree.put(u, 0);
        }
        
        for (Character u : graph.keySet()) {
            for (Character v : graph.get(u)) {
                indegree.put(v, indegree.get(v) + 1);
            }
        }     
        
        return indegree;
    }

    private String topologicalSorting(Map<Character, Set<Character>> graph) {
        // as we should return the topo order with lexicographical order
        // we should use PriorityQueue instead of a FIFO Queue
        Map<Character, Integer> indegree = getIndegree(graph);
        Queue<Character> queue = new PriorityQueue<>();
        
        for (Character u : indegree.keySet()) {
            if (indegree.get(u) == 0) {
                queue.offer(u);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Character head = queue.poll();
            sb.append(head);
            for (Character neighbor : graph.get(head)) {
                indegree.put(neighbor, indegree.get(neighbor) - 1);
                if (indegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        if (sb.length() != indegree.size()) {
            return "";
        }
        return sb.toString();
    }
}           

更多題解參考：

九章官網solution