14. 最长公共前缀
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例：
- 输入：
strs = ["flower","flow","flight"]→ 输出："fl" - 输入：
strs = ["dog","racecar","car"]→ 输出：""（不存在公共前缀）
约束：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
解题思路
第一步：理解问题本质
"最长公共前缀"意味着：从第 0 个字符开始，找到所有字符串共同拥有的最长连续字符序列。
关键洞察：公共前缀不可能比任何一个字符串更长。因此，一旦某个字符串在某个位置与其他字符串不同（或已经到达该字符串末尾），公共前缀就在此终止。
第二步：暴力解法
最直觉的方法是两两合并：先求前两个字符串的公共前缀，再用结果与第三个字符串求公共前缀，依此类推。
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
# 空数组没有公共前缀可言，防御性返回空串
if not strs:
return ""
# 求两个字符串的公共前缀
def common_prefix(a: str, b: str) -> str:
i = 0
# 三个条件缺一不可：两个串都还没到头，且当前字符相同
# 任一条件不成立，公共前缀就在 i 处终止
while i < len(a) and i < len(b) and a[i] == b[i]:
i += 1
return a[:i]
# 以第一个字符串为起点，逐个「吸收」后面的串：前缀只会越并越短
prefix = strs[0]
for s in strs[1:]:
prefix = common_prefix(prefix, s)
if not prefix: # 提前终止：前缀已经空了，后面再怎么并也不会变回来
return ""
return prefix
时间复杂度：O(n * m)，其中 n 为字符串数量，m 为最短字符串长度。
为何还能更直接：两两合并引入了一个辅助函数和中间变量，逻辑绕了一圈。实际上可以直接按"列"比较，更直观——固定列索引 i，检查所有字符串第 i 个字符是否相同。
第三步：优化解法（纵向逐列比较）
以第一个字符串为"参照"，逐字符（逐列）向右扫描，对每一列检查所有字符串在该位置的字符是否与参照字符一致。只要发现不一致，立刻返回当前已确认的前缀。
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
# 空数组直接返回空串，避免下面取 strs[0] 越界
if not strs:
return ""
# 以第一个字符串为基准，逐字符比较
# i 是列下标（所有字符串的第 i 个字符），char 是基准串在这一列的字符
for i, char in enumerate(strs[0]):
for s in strs[1:]:
# 两种终止条件：
# 1. 当前字符串已到末尾（i >= len(s)）
# 2. 当前字符与基准字符不同
# 顺序不能反：先判越界再取 s[i]，靠 or 的短路避开下标错误
if i >= len(s) or s[i] != char:
# 第 i 列已经不匹配，公共前缀就是前 i 列
return strs[0][:i]
# 所有字符都匹配，第一个字符串本身就是公共前缀
return strs[0]
第四步：最优解法（二分查找）
理论上还可以用二分查找缩小前缀长度范围：最长公共前缀的长度一定在 [0, min_len] 之间（min_len 为最短字符串长度），对这个范围二分，每次检查候选长度是否是公共前缀。
但对于本题，二分查找的时间复杂度为 O(n * m * log m)，反而比纵向比较的 O(n * m) 更慢，因此纵向逐列比较就是实际最优解法，二分查找仅作为思路扩展了解即可。
完整代码实现
算法可视化 · 逐帧回放这道题的代码20 帧 · 录制输入 ["flower","flow","flight"]
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 空数组没有公共前缀，同时也避免下面取 strs[0] 越界
if not strs:
return ""
# 外层按「列」扫描：i 是字符下标，char 是第一个字符串在该列的字符
for i, char in enumerate(strs[0]):
# 内层把这一列拿去和其余每个字符串比
for s in strs[1:]:
# 先判 i 是否超出该串长度（更短的串会先到头），再比字符；
# 用 or 的短路特性保证不会先访问 s[i]
if i >= len(s) or s[i] != char:
# 第一处不一致出现，公共前缀就定格在前 i 个字符
return strs[0][:i]
# 基准串整体都被所有串共享，它自己就是最长公共前缀
return strs[0]
示例推演
以 strs = ["flower", "flow", "flight"] 为例，期望输出 "fl"。
以 strs[0] = "flower" 为基准，逐列检查：
第 0 列，i = 0，char = 'f'：
"flow"[0] = 'f'=='f'，通过"flight"[0] = 'f'=='f'，通过- 本列全部通过，继续
第 1 列，i = 1，char = 'l'：
"flow"[1] = 'l'=='l'，通过"flight"[1] = 'l'=='l'，通过- 本列全部通过，继续
第 2 列，i = 2，char = 'o'：
"flow"[2] = 'o'=='o'，通过"flight"[2] = 'i'!='o'，不匹配！- 立刻返回
strs[0][:2]="fl"
最终结果："fl"，正确。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力（两两合并） | O(n * m) | O(m) | 需存储中间前缀变量 |
| 最优（纵向逐列） | O(n * m) | O(1) | 无额外空间，提前终止更快 |
| 二分查找 | O(n * m * log m) | O(m) | 理论有趣但实际更慢 |
n 为字符串数量，m 为最短字符串长度。两种主流方法时间复杂度相同，纵向比较空间更优且实现更简洁。
易错点总结
- 越界检查优先于字符比较：在判断
s[i] != char之前，必须先判断i >= len(s)，否则当某个字符串比基准字符串短时会触发索引越界错误。代码中使用or的短路特性，先检查越界条件。 - 空数组的处理：题目约束保证数组非空，但防御性地加上
if not strs是良好习惯。 - 返回值的切片：返回
strs[0][:i]而非strs[0][:i+1]，因为在发现第i列不匹配时，公共前缀是第0到i-1列，共i个字符，Python 切片[:i]恰好取前i个字符（不含第i个）。
扩展思考
- 字典序排序优化：若先对字符串数组排序，最长公共前缀只需比较排序后的第一个和最后一个字符串即可（因为排序后差异最大的就是首尾两个）。这在字符串数量很多但最长公共前缀很短时可以显著减少比较次数。
- 本题核心：这道题考查的是对"逐列扫描"思维的运用——将二维问题（多字符串 × 多字符）转化为按列逐步确认的线性扫描，遇到第一个不匹配就停止，避免无效计算。