外星词典如何从单词顺序推导字符拓扑序？

简化版

外星词典把字符看成图节点。比较相邻两个单词，找到第一个不同字符 a 和 b，就能推导出边 a -> b，表示 a 在字母表中排在 b 前面。建完图后做拓扑排序；如果有环或前缀非法，返回空。

详细版

只比较相邻单词，因为词典整体已排序，相邻单词提供的约束足够。对每对相邻单词，找到第一个不同字符，加入有向边；如果没有不同字符，但前一个单词更长，比如 abc 在 ab 前面，则排序不可能成立。

建图后用 Kahn 算法统计入度，从入度为 0 的字符开始输出。若输出字符数小于所有出现字符数，说明存在环，返回空。复杂度主要是扫描所有字符和边，约 O(totalChars + E)。

完整版教学

一、题目到底在推什么

题目给的是按外星字母序排好的单词列表，但不知道字符顺序。我们要从“为什么 word[i] 能排在 word[i+1] 前面”中提取字符先后约束。

["wrt", "wrf"]
比较:
w = w
r = r
t != f
推出: t -> f

第一个不同字符决定两个单词的字典序，后面的字符不再提供约束。所以只取第一个不同字符，不能把后续所有不同字符都连边。

二、为什么只比较相邻单词

排序列表中的相邻单词已经包含局部顺序约束。非相邻单词的关系通常可以由相邻关系传递得到，或者即便补充比较也不会比相邻比较更可靠。经典做法就是比较 words[i] 和 words[i+1]。

例如：

wrt < wrf  => t -> f
wrf < er   => w -> e
er  < ett  => r -> t
ett < rftt => e -> r

这些边连起来得到 w -> e -> r -> t -> f。如果拿 wrt 和 er 比，也能得到 w -> e，但它已经由相邻对提供了。

三、前缀非法是特殊陷阱

如果两个相邻单词没有找到不同字符，说明较短词应该排在较长词前面。若较长词反而在前，例如 ["abc", "ab"]，无论字符顺序怎么排都不合法。

合法:   ab < abc
非法:   abc < ab

这个情况不会产生字符边，但必须立刻返回空。很多错误代码只在有不同字符时建边，忽略前缀非法，导致错误通过不了关键用例。

四、建图和去重边

所有出现过的字符都要加入图，即使它没有任何边。否则最后输出可能漏字符。建边时最好用 Set<Character> 存邻居，避免重复边导致入度被重复增加。

Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> indeg = new HashMap<>();
for (String w : words) {
    for (char ch : w.toCharArray()) {
        graph.putIfAbsent(ch, new HashSet<>());
        indeg.putIfAbsent(ch, 0);
    }
}

如果同一条边 a -> b 被重复加入两次，而入度加了两次，Kahn 算法就可能永远无法把 b 的入度减到 0。因此边去重不是优化，而是正确性细节。

五、Kahn 拓扑排序输出字符序

建好有向图后，入度为 0 的字符表示当前没有已知前置字符，可以先输出。每输出一个字符，就删除它的出边，让后继字符入度减 1。

queue = all chars with indegree 0
while queue not empty:
  ch = poll()
  append ch
  for next in graph[ch]:
    indeg[next]--
    if indeg[next] == 0: offer next

如果最终输出长度小于字符总数，说明存在环。例如 a -> b -> a，两个字符都互相要求排在对方前面，不可能得到合法字母序。

六、答案不唯一怎么处理

当队列里同时有多个入度为 0 的字符时，说明这些字符之间没有被题目约束，输出任意一个都可能合法。除非题目要求字典序最小答案，否则不需要用优先队列。

场景	处理
输出任意合法顺序	普通队列
输出字典序最小合法顺序	小根堆
判断是否唯一	每轮队列大小必须为 1

面试追问“答案是否唯一”时，可以说：拓扑排序通常不唯一，如果某一轮有多个零入度节点，就存在多个合法选择。

七、常见误区与追问

记忆钩子：外星词典不是比较所有字符，而是从相邻单词的“第一个不同字符”抽一条有向边。

误区：把两个单词所有不同字符都建边。 字典序只由第一个不同字符决定，后续字符不能推出相对顺序。
误区：漏掉没有边的字符。 所有出现过的字符都要进入图，否则输出不完整。
误区：忽略 abc 在 ab 前面的前缀非法。 这种情况没有可用字符顺序能解释，必须返回空。
追问：为什么要边去重？ 重复边会重复增加入度，导致后继节点无法正确归零。
追问：如何检测环？ 拓扑输出字符数小于总字符数，或 DFS 三色遇到回边，都说明有环。
追问：多个答案怎么办？ 普通题返回任意合法拓扑序；若要求最小字典序，用优先队列选零入度字符。

八、加强记忆

外星词典的流程是：收集所有字符，比较相邻单词，取第一个不同字符建有向边，检查前缀非法，最后拓扑排序。它考的是“字符串顺序约束转图”的能力，而不是单纯排序。第一个不同字符、边去重、所有字符入图、拓扑判环，是四个最容易丢分的点。

简化版

详细版