题目与适用场景
给定一个非空小写 ASCII 字符串数组 words，数组声称已经按照某个未知字母表排序。请返回一个 包含输入中所有不同字符、且每个字符恰好出现一次的顺序，使整个单词列表保持有序。若不存在这样 的顺序，返回空字符串。存在多个可行字母表时，返回任意一个即可。
本题假设单词数不超过 10,000，总字符数不超过 100,000；这些是面试练习约束，不代表特定平台 限制。["wrt", "wrf", "er", "ett", "rftt"] 的一个答案是 "wertf"。 ["abc", "ab"] 无解，因为较长单词排在自身前缀之前；["z", "x", "z"] 同时要求 z < x 和 x < z，也无解。
难点发生在拓扑排序之前。输入只有已排序单词，图的边需要推导。解法必须只提取字典序真正支持 的约束，保留没有边的字符，并分别处理前缀矛盾与有向环。
面试官在考察什么
第一个信号是能否从相邻单词的首个不同字符推导边。"wrt" 排在 "wrf" 前面，只能证明 t < f。首个差异已经决定这对单词的字典序，后续位置无法再提供这对单词的字符先后关系。
第二个信号是前缀规则。共同部分完全相同时，较短单词必须在前。"ab" 位于 "abc" 前面 合法且不新增边；"abc" 位于 "ab" 前面与任何字母表都冲突。单独运行拓扑排序发现不了 该问题，因为这对单词不会产生不同字符。
第三个信号是建图是否完整。每个出现过的字符都要成为节点，包括单词中没有任何边的孤立字符。 同一条边出现多次时，入度只能增加一次；为每个源字符使用邻接集合可以保持邻接关系与入度一致。
最后考察证明与验证。Kahn 算法只有处理完全部节点才能返回完整顺序；结果较短说明剩余图中有环。 某一步同时出现多个零入度字符，表示证据无法确定唯一字母表，但在基础题契约中依然有效。
回答前要先确认的问题
- 输入是否包含字母表中的所有字符？ 本解法只排列单词中出现过的字符。没有外部字母表定义，
就无法补充或放置未出现字符。
- 任意有效顺序都可以吗？ 基础题允许任意答案。若要求按常规字符顺序最小，需要最小堆，
复杂度也会变化。
- 怎样表示无解？ 本题对无效前缀和环都返回空字符串。生产接口可以返回结构化原因与证据。
- 字符的定义是什么？ 基础输入只含小写 ASCII。Unicode 码点或字素簇需要先约定分词规则。
- 单词可以重复吗？ 可以。两个相同的相邻单词不增加约束，也不会让输入无效。
- 必须存在唯一字母表吗？ 不需要。追问可以通过每一步零入度候选数判断唯一性。
- 数组可以为空吗？ 本版本至少包含一个非空单词。若允许空输入，要先确认返回空字母表还是
报告请求无效。
30 秒回答框架
“我会为每个不同字符建立节点。逐对比较相邻单词，只扫描到第一个不同位置，并从前一个单词的 字符向后一个单词的字符连边。若没有不同字符且前一个单词更长，就出现了较长单词排在自身前缀 之前的矛盾，直接返回空字符串。建图时对边去重并维护入度，再从所有零入度字符开始执行 Kahn 拓扑排序。处理完所有节点就得到满足全部约束的顺序；结果较短说明存在环。总时间为输入字符数 加图规模的线性复杂度，多种拓扑顺序都可作为答案。”
分步骤深入解答
记 C 为所有单词的总字符数，U 为不同字符数，E 为不同先后边数。先为每个已出现字符创建 邻接集合 graph[ch] 和初始值为零的 indegree[ch]。这个步骤必须在比较单词前完成：一个字符 即使没有约束也是合法节点，不能只从边的端点收集字符。
只比较相邻单词就足够。若返回的字母表能证明每一对相邻单词有序，传递性会保证整个列表有序； 同时也避免比较平方数量的单词对。对 first 与 second 扫描到较短长度：
- 首次遇到
first[i] != second[i]时，添加first[i] -> second[i]，并停止比较该词对。 - 所有共同位置都相同且
first更长时，返回空字符串。 - 所有共同位置都相同且
first不更长时，不新增边。
只有新边插入邻接集合时才增加目标字符入度。例如 "za" < "zb" 与 "ca" < "cb" 都 推出 a -> b。若将其计数两次，移除 a 后 b 的入度仍大于零，合法输入会被误判成环。
Kahn 算法把所有零入度字符放入队列。它维护两个不变量：每个未处理字符的入度等于其他未处理 字符指向它的边数；队列恰好包含没有未处理前驱的字符。弹出队首字符是安全的，随后遍历其出边 并减少邻居入度；邻居的最后一个前驱消失时进入队列。
from collections import deque
def alien_order(words: list[str]) -> str:
graph = {char: set() for word in words for char in word}
indegree = {char: 0 for char in graph}
for first, second in zip(words, words[1:]):
limit = min(len(first), len(second))
for index in range(limit):
before = first[index]
after = second[index]
if before == after:
continue
if after not in graph[before]:
graph[before].add(after)
indegree[after] += 1
break
else:
if len(first) > len(second):
return ""
ready = deque(
char for char, degree in indegree.items() if degree == 0
)
order: list[str] = []
while ready:
char = ready.popleft()
order.append(char)
for neighbor in graph[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
ready.append(neighbor)
return "".join(order) if len(order) == len(indegree) else ""正确性分为两层。建图具有可靠性：每条边都来自相邻单词的首个差异，因此任何可行字母表都必须 满足它；前缀检查排除了没有不同字符却依然无序的唯一相邻场景。拓扑排序也具有可靠性：队列不变量 保证输出字符位于所有已推导前驱之后。于是每一对相邻单词都有序，整个列表也有序。
若算法输出少于 U 个字符，剩余节点的入度都大于零。从任意剩余节点反复沿入边前进，在有限图 中必然再次遇到某个节点，重复部分构成有向环，线性字母表无法满足它。反过来，无环图总有零入度 节点，所以 Kahn 算法最终会处理全部节点并返回有效顺序。
初始化节点并扫描相邻单词需要 O(C)，Kahn 算法各处理节点和不同边一次，总时间为 O(C + U + E)，额外空间为 O(U + E)。小写 ASCII 下 U 最多为 26，但保留符号表达更便于 迁移到其他字母表。
多解时，测试应验证性质。非空结果必须恰好包含全部不同字符一次；建立字符排名后，按返回顺序 重新比较每对相邻单词，并单独检查较长单词是否排在自身前缀前。用例要覆盖单个单词、重复单词、 孤立字符、重复边证据、合法前缀、无效前缀、环、长链，以及同时存在多个零入度节点的图。
三色 DFS 也是正确替代方案：遇到灰色节点代表环，退出递归时记录节点并反转后序结果。Kahn 算法 能直接从候选集合观察多解，也没有递归深度问题，因此更适合本题契约。
高质量示范回答
“我先从已排序单词中提取偏序。每个出现过的字符都建立节点，即使它没有任何边。逐对比较相邻 单词并找到首个不同字符：例如 wrt 与 wrf 推出 t -> f，此后的位置不能再影响这对单词 的比较。若没有不同字符，而前一个单词更长，例如 abc 位于 ab 前面，输入已经矛盾。
邻接表使用集合，同一先后关系只增加一次入度。随后执行 Kahn 算法：所有零入度字符先入队， 每次输出一个字符、删除它的出边，并在邻居入度降为零时入队。队列中的字符在未处理图中没有前驱， 所以每次选择都不会违反已知约束。
若结果长度等于不同字符数，每条推导出的边都得到满足，加上前缀检查即可证明每对相邻单词有序， 进而证明整个列表有序。若长度更短，剩余图存在环，没有任何字母表能解释输入。时间复杂度是 O(C + U + E)，空间复杂度是 O(U + E)。我会测试无效前缀、两边构成的环、同一边重复出现、 单个单词和多解；多解用例验证顺序性质，不固定比较某一个字符串。”
常见错误
- 把词对中每个不同位置都连边 → 首个差异后的位置不再参与字典序判断 → **只添加首个差异
对应的边并立即停止。**
- 只执行拓扑排序 →
"abc"位于"ab"前面时没有边可暴露错误 → **比较词对时检查较长
单词先于自身前缀的矛盾。**
- 只为边的端点建节点 → 孤立字符从答案消失 → 为所有出现过的字符预先建节点。
- 重复边重复增加入度 → 合法节点永远无法降到零入度 → 用邻接集合，并只在首次插入时增加。
- 队列为空就返回部分结果 → 有环输入被报告为成功 → 要求结果长度等于不同字符数。
- 只接受一个固定字符串 → 一个偏序可能有多种线性扩展 → 检查字符集合、边和单词相对顺序。
- 比较所有单词对 → 单词数量维度可能出现平方级工作 → 相邻比较已足以建立列表有序性。
- 把多解当作无效 → 多个字母表可以同时解释现有证据 → 基础契约下返回任意有效顺序。
追问与应答
追问 1：怎样判断字母表是否唯一？
Kahn 算法每次弹出前检查候选集合。只要某一步有两个以上零入度字符，就至少存在两种选择顺序， 证据无法确定唯一字母表。若每一步候选数都恰好为一且处理完全部节点，顺序唯一；提前出现空集合 仍表示有环。
追问 2：怎样返回常规字符顺序下最小的有效结果？
把普通队列换成按宿主语言字符顺序排列的最小堆。每次选择当前可行字符中的最小者，可用交换论证 证明得到最小线性扩展。时间变为 O(C + E + U log U)；这个排序只是外部打破平局的规则，不属于 外星字母表本身。
追问 3：怎样返回可操作的无效原因？
前缀矛盾可以返回相邻单词及其下标。Kahn 算法停滞后，在剩余图上运行带父指针的三色 DFS，遇到 灰色节点时还原一条环。结构化结果可区分 invalid_prefix、cycle 与 valid，无需让空字符串 承担全部语义。
追问 4：可以流式处理单词吗？
保留前一个单词；每读到下一个单词就补充节点并推导这一对相邻约束。图和入度仍要保存到流结束， 因为后续证据可能增加前驱或形成环。除非数据源提供明确结束边界，否则不能提前确认最终拓扑顺序。
追问 5：怎样枚举所有有效字母表？
对当前所有零入度字符回溯：选择一个、暂时删除其出边、递归，再恢复状态。这样只枚举合法顺序， 但输出数量可能接近 U!；实现前应确认字母表规模或最大输出数量。
追问 6：Unicode 单词需要改什么？
先定义比较单位。码点不一定等于用户看到的字符，区域排序还可能处理规范化形式或多码点序列。 按照题目约定把单词切成字母表符号，仅在契约要求时规范化，然后对这些 token 运行同一套图算法。 缺少该契约时，“字符顺序”本身没有完整定义。