题目重点：从已排序单词推导字符先后，正确去重入度，检测前缀错误与环，并返回确定的拓扑顺序。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入单词已按某未知字符序排序；只需为出现过的字符找一种满足顺序的全序。
- 训练多解时用Python字符比较下最小的可行全序；非法排序返回None，空词表或只含空词返回空字符串。
- 相同词可重复；短词是长词前缀时短词在前合法，长词在前不合法。
解题路线
- 先为每个出现过的字符建节点，即使它没有产生任何边。不能只登记相邻单词的首个差异，否则单字词、重复词和孤立字符会从答案消失。
- 逐对比较相邻单词，仅首个不同字符x、y说明x必须先于y；找到后立即break。后面的不同位置不提供约束，因为字典序已在首差异决定大小。所有相邻对满足顺序就足以让整个列表有序。
- 若没有差异且前词更长，前词是后词的严格扩展，任何字母顺序都无法修复这个前缀错误。必须在建图时直接拒绝，不能等待环检测。
- 边用集合记录。只有y尚不在graph[x]时，才插入并增加indegree[y]。Kahn删除的是每条不同边一次；若插边去重但入度每次都加，节点会留下虚假的正入度，被误判为环。
- 把所有零入度节点加入小根堆，每次取可放的最小字符，处理其出边并释放新的零入度节点。这产生字典序最小的合法拓扑序；如果只要求任一结果，普通队列也可并省去堆成本。
- 输出数量小于节点数表示仍有环，无法全序化。不能把部分前缀返回成有效字典。入度归零才入堆，图和入度都已去重时每个节点最多加入一次。
- 独立核验可以穷举短字母表的全排列，把每个原单词转换成该序下的rank元组，检查整个词表是否保持排序；这个对照不复用首差异建图，能一起发现前缀和重复边错误。
手动走一遍
[za,zb,ca,cb]中两次得到a→b，同时得到z→c；a→b只计一条边。本文字符比较规则下最小全序abzc满足两条约束。[abc,ab]是无效前缀；[z,x,z]得到z→x→z，无解。[a,a]仍要返回a。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import heapq
def alien_order(words):
graph = {c: set() for word in words for c in word}
indegree = {c: 0 for c in graph}
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
if y not in graph[x]:
graph[x].add(y)
indegree[y] += 1
break
else:
if len(a) > len(b):
return None
ready = [c for c in graph if indegree[c] == 0]
heapq.heapify(ready)
result = []
while ready:
c = heapq.heappop(ready)
result.append(c)
for other in graph[c]:
indegree[other] -= 1
if indegree[other] == 0:
heapq.heappush(ready, other)
return ''.join(result) if len(result) == len(graph) else None
复杂度
设字符出现总量S、单词数W、不同字符数C、不同边数E，建图O(S+W)，堆拓扑O(E+C log C)，空间O(C+E)加输出。集合操作按平均常量；相邻pair比较总字符扫描为O(S)。
易错点与追问
容易失分的边界
- 每个不同位置都加边，没有停在首差异。
- 边去重但入度不去重。
- 遗漏没有边的字符。
- 不检查无效前缀，或把部分拓扑结果当成功。
继续深挖
- 如何判断顺序是否唯一？
- 只需任意答案时如何降去堆开销？
- 词表追加一个词怎样维护约束？
- 如果已知完整字母表，未出现字符怎样纳入多解政策？
