🔴 剑指 Offer II 114. 外星文字典

LeetCode 提示

题目难度 困难

原题链接 🔗 leetcode

题解1

参考题解。

整体分为两个步骤，1是建立拓扑图，2是拓扑排序。拓扑排序使用BFS+入度表实现，可以参考剑指offer专项版113题。

建立拓扑图需要注意：

1. 只需要关注相邻两个单词第一个不相同的字母即可，处理完第一个不同字母之后即可继续下一组单词
2. 给的字典可能就是错的，例如abc ab是不应该出现的

这道题难点主要在于需要自己建立拓扑图。

class Solution {    public String alienOrder(String[] words) {        Map<Character, List<Character>> routes = new HashMap<>();        int[] inDegrees = new int[26];
        for (String word : words) {            for (int i=0; i<word.length(); i+=1) {                routes.putIfAbsent(word.charAt(i), new ArrayList<>());            }        }
        for (int i=1; i<words.length; i+=1) {            String s1 = words[i-1], s2 = words[i];            int n1 = s1.length(), n2 = s2.length();            if (n1 > n2 && s1.startsWith(s2)) {                return "";            }
            for (int j=0; j<Math.min(n1, n2); j+=1) {                char c1 = s1.charAt(j), c2 = s2.charAt(j);                if (c1 != c2) {                    routes.get(c1).add(c2);                    inDegrees[c2-'a'] += 1;                    break;                }            }        }
        Queue<Character> queue = new LinkedList<>();        int totalSize = routes.size();        StringBuilder sb = new StringBuilder();
        for (char key : routes.keySet()) {            if (inDegrees[key-'a'] == 0) {                queue.offer(key);            }        }
        while (!queue.isEmpty()) {            char left = queue.poll();            sb.append(left);                        for (char right : routes.get(left)) {                if (--inDegrees[right-'a'] == 0) {                    queue.offer(right);                }            }        }
        if (sb.length() == totalSize) {            return sb.toString();        }
        return "";    }}