面试算法114：外星文字典

题目

一种外星语言的字母都是英文字母，但字母的顺序未知。给定该语言排序的单词列表，请推测可能的字母顺序。如果有多个可能的顺序，则返回任意一个。如果没有满足条件的字母顺序，则返回空字符串。例如，如果输入排序的单词列表为[“ac”，“ab”，“bc”，“zc”，“zb”]，那么一个可能的字母顺序是"acbz"。

分析

在排序的单词列表[“ac”，“ab”，“bc”，“zc”，“zb”]中，一共出现了4个字母，即’a’、‘b’、‘c’和’z’。需要根据单词的顺序确定这个4个字母的顺序。由于"ac"排在"ab"的前面，因此字母’c’应该排在字母’b’的前面（即’c’＜’b’）。这是因为这两个单词的第1个字母相同，第2个字母不同，那么它们的第2个字母的顺序确定了两个单词的顺序。接下来两个相邻的单词是"ab"和"bc"，它们的第1个字母就不同，那么它们的顺序由它们的第1个字母确定，所以’a’＜’b’。类似地，可以根据"bc"排在"zc"的前面得知’b’＜’z’，根据"zc"排在"zb"的前面得知’c’＜’b’。
在构建有向图之后，采用广度优先搜索实现拓扑排序。队列中保存的是入度为0的节点。每次从队列中取出一个节点，将该节点添加到拓扑排序序列中（即字母顺序序列），然后找到比该字母大的字母并将它们节点的入度减1，这相当于删除一条从较小的字母指向较大的字母的边。如果发现新的入度为0的节点，则将其添加到队列中。重复这个过程直到队列为空，此时要么图中所有节点都已经访问完毕，已经得到了完整的拓扑排序序列；要么剩下的还没有搜索到的节点形成一个环，已经不存在入度为0的节点。

解

public class Test {
    public static void main(String[] args) {
        String[] words = {"ac", "ab", "bc", "zc", "zb"};
        String result = alienOrder(words);
        System.out.println(result);
    }

    public static String alienOrder(String[] words) {
        // graph以邻接表的形式表示，与某节点相邻的节点用一个HashSet保存
        Map<Character, Set<Character>> graph = new HashMap<>();
        // inDegrees保存每个节点的入度
        Map<Character, Integer> inDegrees = new HashMap<>();
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                graph.putIfAbsent(ch, new HashSet<>());
                inDegrees.putIfAbsent(ch, 0);
            }
        }

        for (int i = 1; i < words.length; i++) {
            String w1 = words[i - 1];
            String w2 = words[i];
            if (w1.startsWith(w2) && !w1.equals(w2)) {
                return "";
            }

            for (int j = 0; j < w1.length() && j < w2.length(); j++) {
                char ch1 = w1.charAt(j);
                char ch2 = w2.charAt(j);
                if (ch1 != ch2) {
                    if (!graph.get(ch1).contains(ch2)) {
                        graph.get(ch1).add(ch2);
                        inDegrees.put(ch2, inDegrees.get(ch2) + 1);
                    }

                    break;
                }
            }
        }

        Queue<Character> queue = new LinkedList<>();
        for (char ch : inDegrees.keySet()) {
            if (inDegrees.get(ch) == 0) {
                queue.add(ch);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char ch = queue.remove();
            sb.append(ch);
            for (char next : graph.get(ch)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0) {
                    queue.add(next);
                }
            }
        }

        return sb.length() == graph.size() ? sb.toString() : "";
    }

}