当前位置：首页 > news >正文

解密火星文：LeetCode 269 题详解与 Swift 实现

news 2025/5/10 6:12:46

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 构建图（Graph）
  - 拓扑排序（Topological Sort）
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 实际场景类比
- 总结

摘要

这篇文章我们来聊聊 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 = falsefor 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 = truebreak}}// 无效的前缀情况（如 ["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]! -= 1if 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"]))
// 输出: ""（非法前缀）