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

每日算法 -【Swift 算法】查找字符串数组中的最长公共前缀

ai 2025/7/13 22:33:47

Swift 实现：查找字符串数组中的最长公共前缀

在面试或实际开发中，我们常常会遇到需要在一组字符串中找出它们的最长公共前缀的问题。

例如，输入：

["flower", "flow", "flight"]

输出应为：

"fl"

如果不存在公共前缀，则应返回空字符串 ""。

🧠 解题思路

最长公共前缀的本质是找出所有字符串从左开始一致的部分。思路上有三种主流方式：

逐步比较法（横向扫描）
逐字符比较法（纵向扫描）
排序后只比较首尾字符串

1️⃣ 方法一：逐步比较法（横向扫描）

以第一个字符串为初始前缀，逐个与后面的字符串比较并修剪前缀，直到不再能修剪为止。

/// 方法一：横向扫描
/// - Parameter strs: 字符串数组
/// - Returns: 最长公共前缀
func longestCommonPrefix_Horizontal(_ strs: [String]) -> String {// 如果数组为空，直接返回空字符串guard let first = strs.first else { return "" }// 初始前缀设为第一个字符串var prefix = first// 遍历剩下的字符串for str in strs.dropFirst() {// 如果当前字符串不以 prefix 开头，就逐步去掉 prefix 的最后一个字符while !str.hasPrefix(prefix) {prefix = String(prefix.dropLast())// 如果前缀被减到空字符串，说明没有公共前缀if prefix.isEmpty {return ""}}}return prefix
}

🔍 适合场景：数据量较小，或字符串之间前缀相差较大时。

2️⃣ 方法二：逐字符比较法（纵向扫描）

逐列检查每个字符串相同位置的字符，一旦发现不同或越界，即可确定前缀。

/// 方法二：纵向扫描
/// - Parameter strs: 字符串数组
/// - Returns: 最长公共前缀
func longestCommonPrefix_Vertical(_ strs: [String]) -> String {// 如果数组为空，直接返回空字符串guard let first = strs.first else { return "" }// 遍历第一个字符串的每个字符（按下标索引）for i in first.indices {let char = first[i]// 遍历其他所有字符串for str in strs {// 如果当前字符串已越界或字符不一致，返回当前索引之前的前缀if i >= str.endIndex || str[i] != char {return String(first[..<i])}}}return first
}

🔍 适合场景：前缀较短时效率较高，因为可以提早中止。

3️⃣ 方法三：排序法

对数组排序，最长公共前缀一定存在于排序后的第一个和最后一个字符串之间。

/// 方法三：排序法
/// - Parameter strs: 字符串数组
/// - Returns: 最长公共前缀
func longestCommonPrefix_Sorting(_ strs: [String]) -> String {// 空数组直接返回guard !strs.isEmpty else { return "" }// 字符串排序后，前缀只需比较首尾两个字符串let sortedStrs = strs.sorted()let first = sortedStrs.first!let last = sortedStrs.last!var i = first.startIndex// 从头开始逐个字符比较while i < first.endIndex && first[i] == last[i] {i = first.index(after: i)}// 返回首尾相同的前缀部分return String(first[..<i])
}

🔍 适合场景：当字符串数量不多、排序成本可接受时非常简洁有效。

📈 时间复杂度对比

方法	时间复杂度	空间复杂度	特点
横向扫描法	`O(N * M)`	`O(1)`	简单直观，易于理解
纵向扫描法	`O(N * M)`	`O(1)`	提前结束判断更高效
排序法	`O(N log N + M)`	`O(log N)`	代码最简洁，依赖排序开销

其中：

N 为字符串数组的长度
M 为最短字符串的长度

✅ 总结

策略名称	适合场景	优点	缺点
横向扫描	字符串之间差异较大	实现简单，逻辑清晰	前缀缩减较慢，效率一般
纵向扫描	公共前缀较短或数据量大时	可提早中止，更高效	代码略复杂
排序法	字符串数量不多且排序代价可接受	实现简洁，只比较首尾两个	有排序开销