题目描述
思路解析动画文字版
记住这一句：相邻差异 = 有向边，拓扑排序 = 字母全序。下面一步步建图再排序。
先把出现过的 5 个字母 w、e、r、t、f 摆成节点，入度都标 0。接下来逐对相邻单词比较，连出有向边。
比较 "wrt" 和 "wrf"：逐位对齐，第 3 位首次不同——'t'（在前面的词里）对上 'f'。高亮这两个字母。
'wrt' 排在 'wrf' 前面 → 在这门语言里 t < f。连有向边 t→f，'f' 的入度 +1（看它上方）。
比较 "wrf" 和 "er"：逐位对齐，第 1 位首次不同——'w'（在前面的词里）对上 'e'。高亮这两个字母。
'wrf' 排在 'er' 前面 → 在这门语言里 w < e。连有向边 w→e，'e' 的入度 +1（看它上方）。
比较 "er" 和 "ett"：逐位对齐，第 2 位首次不同——'r'（在前面的词里）对上 't'。高亮这两个字母。
'er' 排在 'ett' 前面 → 在这门语言里 r < t。连有向边 r→t，'t' 的入度 +1（看它上方）。
比较 "ett" 和 "rftt"：逐位对齐，第 1 位首次不同——'e'（在前面的词里）对上 'r'。高亮这两个字母。
'ett' 排在 'rftt' 前面 → 在这门语言里 e < r。连有向边 e→r，'r' 的入度 +1（看它上方）。
建图完成（w→e、e→r、r→t、t→f）。开始 Kahn 拓扑排序：看节点上方入度，'w' 的入度为 0（没有字母必须排在它前面）→ 入队。
队首 'w' 出队，确定它是当前最靠前的字母，追加到结果："w"。接着删掉它的所有出边。
删除出边 w→e：'e' 的入度减 1，变为 0——降到 0，马上可以入队。
'e' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
队首 'e' 出队，确定它是当前最靠前的字母，追加到结果："we"。接着删掉它的所有出边。
删除出边 e→r：'r' 的入度减 1，变为 0——降到 0，马上可以入队。
'r' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
队首 'r' 出队，确定它是当前最靠前的字母，追加到结果："wer"。接着删掉它的所有出边。
删除出边 r→t：'t' 的入度减 1，变为 0——降到 0，马上可以入队。
't' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
队首 't' 出队，确定它是当前最靠前的字母，追加到结果："wert"。接着删掉它的所有出边。
删除出边 t→f：'f' 的入度减 1，变为 0——降到 0，马上可以入队。
'f' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
队首 'f' 出队，追加到结果。所有 5 个字母都出队、入度全清零——拓扑排序完成！字母全序就是出队顺序 "wertf"，这就是这门火星语言的字典序。
边界先想清。
两个高频追问。
参考代码
def alienOrder(words): g = {c: set() for w in words for c in w} indeg = {c: 0 for c in g} for a, b in zip(words, words[1:]): if len(a) > len(b) and a.startswith(b): return "" # 非法：前缀反序 for x, y in zip(a, b): if x != y: if y not in g[x]: g[x].add(y); indeg[y] += 1 break q = deque([c for c in g if indeg[c] == 0]) out = [] while q: c = q.popleft(); out.append(c) for nb in g[c]: indeg[nb] -= 1 if indeg[nb] == 0: q.append(nb) return "".join(out) if len(out) == len(g) else ""复杂度
- 时间：O(C + ΣL)，ΣL=所有单词总长度（建图），C=不同字母数（拓扑）
- 空间：O(C + E)，邻接表存边 + 入度表 + 队列
易错点
面试追问把动画讲成自己的话
追问为什么用拓扑排序而不是直接排字母？
追问怎么判断输入自相矛盾（无解）？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 站中转内最便宜的航班
LeetCode 787 · 中等 · 沿着 高级图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题