LeetCode【0014】最长公共前缀

本文目录

1 中文题目
2 求解思路
- 2.1 基础解法：排序法
- 2.2 优化解法：滑动窗口法
- 2.3 最优解法：基于python内置函数的横向扫描法
3 题目总结

1 中文题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例：

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

$\leq strs.length \leq 200$
$\leq strs[i].length \leq 200$
$s t rs [i]$ 仅由小写英文字母组成

2 求解思路

2.1 基础解法：排序法

思路

先对字符串数组进行字典序排序，然后只需要比较首尾两个字符串的公共前缀即可。因为字典序排序后，第一个和最后一个字符串的差异最大，它们的公共前缀一定是整个数组的公共前缀。

# 原始数组：["flower", "flow", "flight", "flake"]
sorted_strs = sorted(strs)
# 排序后：["flake", "flight", "flow", "flower"]# 获取首尾字符串
first = "flake"
last = "flower"

Python代码

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:"""使用排序法查找字符串数组中的最长公共前缀思路：1. 对字符串数组进行字典序排序2. 只需比较首尾两个字符串3. 找出它们的公共前缀即为结果参数:strs: 字符串数组，如 ["flower","flow","flight"]返回:最长公共前缀字符串，如 "fl""""# 处理特殊情况if not strs:return ""if len(strs) == 1:return strs[0]# 对字符串数组进行字典序排序# 排序后，第一个和最后一个字符串的差异最大sorted_strs = sorted(strs)# 获取首尾字符串first = sorted_strs[0]last = sorted_strs[-1]# 获取首尾字符串的最短长度min_length = min(len(first), len(last))# 查找公共前缀result = []for i in range(min_length):# 如果字符不同，直接返回当前累积的前缀if first[i] != last[i]:breakresult.append(first[i])# 返回找到的最长公共前缀return ''.join(result)

时空复杂度分析

时间复杂度分析：O(nlogn + m)
- 排序：O(nlogn)，n为字符串数量
- 比较：O(m)，m为最短字符串长度
空间复杂度分析：O(n + m)
- 排序空间：O(n)
- 结果空间：O(m)

2.2 优化解法：滑动窗口法

思路
从第一个字符开始，逐步扩展窗口大小，每次检查所有字符串在当前位置是否具有相同的字符。一旦发现不同字符，立即停止扩展并返回当前的公共前缀。

python代码

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:"""滑动窗口法：使用逐步扩展窗口的方式"""# 处理特殊情况if not strs:return ""# 初始化窗口大小为1prefix = ""min_length = min(len(s) for s in strs)# 逐步扩展窗口for i in range(min_length):current_char = strs[0][i]# 检查所有字符串在当前位置的字符是否相同if all(s[i] == current_char for s in strs):prefix += current_charelse:breakreturn prefix

时空复杂度分析

时间复杂度分析：
- 最好情况：O(n)，n为最短字符串长度
- 最坏情况：O(S)，S为所有字符的总和
- 平均情况：O(n×m)，m为字符串个数
空间复杂度分析：O(1)

2.3 最优解法：基于python内置函数的横向扫描法

思路
使用zip函数将所有字符串按位置压缩，然后逐位比较每个位置上的字符是否相同。当发现不同字符时，即可确定最长公共前缀的长度。

详细步骤解析：

zip函数的工作原理：
- zip(*strs)将所有字符串解包，按位置将字符组合成元组

例如：["abc", "abd", "abf"] 转换为：
('a','a','a') # 第一位
('b','b','b') # 第二位
('c','d','f') # 第三位

enumerate的使用：
- 提供当前处理的位置索引，同时获取当前位置的字符元组。i表示位置，chars表示该位置的所有字符
set去重判断：
- set(chars)将字符元组转为集合，相同字符的集合长度为1，不同字符的集合长度大于1
结果处理：
- 发现不同时返回前i个字符，全部相同时返回最短字符串

示例

# 输入：strs = ["flower","flow","flight"]
# zip(*strs) 生成：
# 第1轮：('f','f','f')   # set长度为1，继续
# 第2轮：('l','l','l')   # set长度为1，继续
# 第3轮：('o','o','i')   # set长度为2，返回"fl"

python代码

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:"""使用zip函数实现 参数:strs: 字符串数组返回:最长公共前缀字符串"""# 处理特殊情况if not strs:return ""# 使用zip函数将所有字符串按位置打包for i, chars in enumerate(zip(*strs)):# 检查当前位置的所有字符是否相同if len(set(chars)) != 1:# 不相同时返回之前的前缀return strs[0][:i]# 所有字符都相同，返回最短字符串return min(strs, key=len)