摘要
这篇文章我们来聊聊 LeetCode 269 题：火星词典（Alien Dictionary）。虽然题目看起来像是在编造一个星球语言，但本质其实是在考察有向图 + 拓扑排序。我们会用 Swift 语言实现一个完整的解法，并通过实际测试场景来验证代码的有效性。同时，还会结合日常开发中“依赖优先级”和“版本管理”等场景类比，帮你更容易理解题目的应用背景。
描述
在一个火星文明中，他们的字母顺序和我们地球的不一样。现在火星人给你一个词典，里面的词都是按照他们的字母顺序排好的。你的任务就是——猜出这个火星语言的字母顺序是什么。
这个词典是一个字符串数组，比如：
let words = ["wrt", "wrf", "er", "ett", "rftt"]
这些字符串就是按火星字典顺序排好的一组词。
我们要根据这些词之间的字母差异，推导出一个可能的字母顺序，比如：
输出: "wertf"
当然，如果有矛盾（比如顺序冲突或者成环），就说明无解，应该返回空字符串。
题解答案
func alienOrder(_ words: [String]) -> String {
var graph = [Character: Set<Character>]()
var inDegree = [Character: Int]()
// 初始化所有字符
for word in words {
for char in word {
graph[char] = Set<Character>()
inDegree[char] = 0
}
}
// 根据相邻词构建有向图
for i in 0..<words.count - 1 {
let first = words[i]
let second = words[i + 1]
let minLen = min(first.count, second.count)
var foundOrder = false
for j in 0..<minLen {
let a = first[first.index(first.startIndex, offsetBy: j)]
let b = second[second.index(second.startIndex, offsetBy: j)]
if a != b {
if !graph[a]!.contains(b) {
graph[a]!.insert(b)
inDegree[b]! += 1
}
foundOrder = true
break
}
}
// 无效的前缀情况（如 ["abc", "ab"]）返回空
if !foundOrder && first.count > second.count {
return ""
}
}
// 拓扑排序
var queue = Array(inDegree.filter { $0.value == 0 }.map { $0.key })
var result = ""
while !queue.isEmpty {
let node = queue.removeFirst()
result.append(node)
for neighbor in graph[node]! {
inDegree[neighbor]! -= 1
if inDegree[neighbor]! == 0 {
queue.append(neighbor)
}
}
}
return result.count == inDegree.count ? result : ""
}
题解代码分析
我们可以把这题拆解成两个步骤：
构建图（Graph）
这就像我们要建立“谁依赖谁”的关系。我们扫描相邻两个词，比如 "wrt" 和 "wrf"，找到第一个不同的字母 t 和 f，我们就可以得出一条边 t -> f，表示 t 在 f 前面。
同时我们也记录每个字母的入度（被多少个其他字母依赖），为下一步做准备。
拓扑排序（Topological Sort）
这一步和“课程表安排”很像。我们找出所有入度为 0 的字符（没有前置依赖的），加入队列，然后不断把它们的“后继节点”的入度减 1。只要哪个节点的入度变成了 0，也加入队列。最终，我们可以排出一个合法的字符顺序。
如果最后排出来的字符个数不等于总字符数，那说明有环（依赖冲突），我们就返回空字符串。
示例测试及结果
print(alienOrder(["wrt", "wrf", "er", "ett", "rftt"]))
// 输出: "wertf"
print(alienOrder(["z", "x"]))
// 输出: "zx"
print(alienOrder(["z", "x", "z"]))
// 输出: ""（有环）
print(alienOrder(["abc", "ab"]))
// 输出: ""（非法前缀）
这些测试用例基本覆盖了以下几种场景：
- 普通字母推理（按字母差异建图）
- 存在环（例如
"z" -> "x"，又"x" -> "z"） - 非法词典排序（前缀冲突）
时间复杂度
- 时间复杂度：O©，其中 C 是所有字符出现的总次数。我们需要遍历每个字符、每对单词比较，并做一次拓扑排序。
- 在最坏的情况下，我们每对字符串都可能建立一个边，所以图构建的复杂度是 O©，排序也是 O©。
空间复杂度
- 空间复杂度：O(U + E)，U 是不同的字母数，E 是图中边的数量。
- 我们使用字典来存图和入度统计，队列用于拓扑排序中间状态。
实际场景类比
你可以把这题理解成一个“依赖管理系统”：
- 每个字母就像一个模块。
- 字典中的词组就像不同的版本组合。
- 根据不同模块在版本中出现的先后顺序，我们可以倒推出它们的依赖关系。
- 而你最后输出的字符串，就是所有模块的加载顺序。
类似的情况你可能在这些地方遇到：
- 构建工具的依赖排序（比如 SwiftPM / CocoaPods）。
- 操作系统驱动加载顺序。
- 前端资源按依赖顺序加载 JS/CSS。
总结
这道题表面是外星人的语言，其实核心考点是如何从局部规则推导出全局顺序，典型的图论思路。在实际项目中，我们常常会遇到“模块依赖冲突”、“加载顺序错乱”的问题，能写出拓扑排序的思维，也能帮助我们理清复杂系统中的“先来后到”。