笔试题“14. 最长公共前缀”看起来是LeetCode上一道安静的基础题但它实际上把字符串处理、边界意识、算法权衡、编码风格都揉在了一起。我在面试时也经常拿它考察候选人的基本功看似人人会写真正写得清爽又经得起追问的却不多。本文直接从题目出发把解题思路、代码实现、复杂度分析和工程化思考一次讲透。1. 题面与核心思路拆解1.1 题目描述与名词澄清题目本身一句话给定一个字符串数组返回所有字符串的公共前缀中最长的那一个如果没有公共前缀返回空字符串。比如[flower, flow, flight]输出是fl如果是[dog, racecar, car]三个字符串从头开始就没有相同的首字符直接返回。很多新手在这里容易把“前缀”和“子串”混淆。前缀是严格从第一个字符开始连续截取的部分比如flow是flower的前缀但low不是。而子串可以是字符串中间的任意连续片段两者完全是两个概念。题目限定了“前缀”就意味着每一步比较都从第0位开始这个问题因此会简单不少。还有一个容易忽略的点题目说的是“所有字符串”的公共前缀不是两两之间最长前缀的简单叠加。两两之间算出的前缀未必是全体的公共前缀。举例来说abc和abd的最长公共前缀是abab和a的公共前缀是a但全体字符串的公共前缀还要先满足第三个字符串所以必须保证每次结果都是跟剩余所有字符串对齐后的才有效。理解了这个约束再去看各种解法思路就顺了。1.2 五种主流解法概览这个题在社区里的热门解法大体有五种横向扫描、纵向扫描、分治法、二分查找、字典树。每个方法都有自己擅长的场景和复杂度特征先放一张对比表后续一步一步展开。解法时间复杂度空间复杂度适用场景横向扫描O(S)S为所有字符总数O(1)最容易想到适合快速写出正确代码纵向扫描O(S)最坏情况同样遍历全部字符O(1)代码精简适合一次性通过所有边界测试分治法O(S)O(m log n)m为最短串长度适合面试展示递归拆解思维二分查找O(S log m)m为最短字符串长度O(1)适合数据量大、单个字符串较长且公共前缀较短的场景字典树O(S) 构建O(m) 查询O(S)适合多次查询、批量处理的前缀匹配场景这里 S 表示全部字符串的字符总数。五种方法归根结底都在做同一件事逐步缩小候选前缀的范围只不过扫描顺序和剪枝策略不同。2. 四种代码级解法实现与要点2.1 横向扫描横向扫描是最好理解的一种。拿第一个字符串作为初始候选前缀用它和第二个字符串求公共前缀得到的中间结果再和第三个字符串求公共前缀一直迭代到最后一个字符串。中间如果公共前缀变成空串说明后面不可能再出现非空公共前缀可以直接返回。def longest_common_prefix(strs: list[str]) - str: if not strs: return prefix strs[0] for s in strs[1:]: prefix common_prefix(prefix, s) if prefix : return return prefix def common_prefix(a: str, b: str) - str: i 0 while i len(a) and i len(b) and a[i] b[i]: i 1 return a[:i]这段代码有两个细节值得注意。第一个是提前终止prefix一旦为空立刻返回后面即使还有几百个字符串也不用再遍历了这是横向扫描最主要的剪枝手段。第二个细节是common_prefix里的索引条件i len(a) and i len(b)两者缺一不可否则短字符串遍历完后继续访问b[i]就会越界。在很多实战场景里我还会额外加一个特判如果数组中只有一个字符串直接返回它本身省掉一次无意义的比较计算。不过这个特判加不加都不影响正确性横向扫描在单元素数组下也会返回strs[0]。2.2 纵向扫描纵向扫描的思路来得更直觉化。把所有字符串竖着排列同一列字符逐个比对先看所有字符串的第0位是否都相同再看第1位是否都相同一直往后推进直到某一位出现不同或者某个字符串已经取完了之前扫描过的列拼接起来就是答案。def longest_common_prefix_vertical(strs: list[str]) - str: if not strs: return for i in range(len(strs[0])): ch strs[0][i] for s in strs[1:]: if i len(s) or s[i] ! ch: return strs[0][:i] return strs[0]这段代码的终止条件写得比较紧凑外层循环以第一个字符串的长度为准内层循环判断其他字符串在当前位置是否越界或字符不一致。一旦触发终止条件返回strs[0][:i]也就是已经通过了所有字符串检查的前缀部分。纵向扫描相比横向扫描有一个天然优势它不需要维护中间变量代码量少且不需要如果公共前缀很短时会在很早期就退出。最坏情况下比如所有字符串相同且很长它确实会扫描完所有字符串的所有位置复杂度为 O(S)。有一个容易忽略的边界情况如果第一个字符串本身是空串外层range(len(strs[0]))根本不会执行函数直接返回结果是正确的。如果数组整体为空开头也做了返回所以两条边界都覆盖到位了。2.3 分治法分治法把这个大问题拆成一个个小问题。将字符串数组从中间分割成左右两半分别计算左右两部分的公共前缀然后再对这两个结果求一次公共前缀合并得到整个数组的答案。递归的终止条件是区间内只剩一个字符串时直接返回它。def longest_common_prefix_divide(strs: list[str], left: int, right: int) - str: if left right: return strs[left] mid (left right) // 2 lcp_left longest_common_prefix_divide(strs, left, mid) lcp_right longest_common_prefix_divide(strs, mid 1, right) return common_prefix(lcp_left, lcp_right)调用方式是longest_common_prefix_divide(strs, 0, len(strs) - 1)。分治法的核心收益在于逻辑上的独立性左右两侧互不干扰分别计算、最后合并天然适合描述为并行任务。单线程下它并不会让时间复杂度假性下降因为每个字符依然至多被比较一次但递归解法在面试里能展示出你对“大问题拆小问题”的敏感度这一点有时候比性能更打动人。需要注意递归的终止条件是left right如果传入一个空数组就会出问题。所以在分治入口处依然要先判断数组是否为空这是递归解法摆脱不了的一层防御。2.4 二分查找二分查找的切入点比较巧妙。公共前缀的长度不可能超过数组中最短字符串的长度所以只需要在[0, shortest_len]这个区间内二分搜索一个最长的可行前缀长度。所谓“可行”就是前mid个字符构成的前缀被所有字符串共享。def longest_common_prefix_binary(strs: list[str]) - str: if not strs: return shortest_len min(len(s) for s in strs) low, high 0, shortest_len while low high: mid (low high 1) // 2 if is_common_prefix(strs, mid): low mid else: high mid - 1 return strs[0][:low] def is_common_prefix(strs: list[str], length: int) - bool: prefix strs[0][:length] for s in strs[1:]: if not s.startswith(prefix): return False return True二分模板里最容易写错的是mid (low high 1) // 2这个细节。因为我们希望寻找“最大的可行长度”属于典型的“找右边界”问题所以中点要向上取整避免在low和high相邻时陷入死循环。如果用(low high) // 2在某种边界下会永远停在同一个low上出不去。这个解法的时间复杂度为 O(S log m)其中 m 是最短字符串的长度。对于“字符串数量不多但单个字符串非常长且公共前缀较短”的场景它往往比横向扫描少做很多无效比较。不过日常编码中使用字符串切片时需要留意 Python 的切片会创建新对象如果 m 很大且每次都要切出前缀内存开销会显著增加底层更稳的做法是改成比较字符下标不真正生成子串。3. 字典树解法和面试进阶讨论3.1 字典树建树与查询字典树Trie提供了另一种持久化的视角。把所有字符串依次插入一棵前缀树公共前缀就是这棵树中从根节点开始、只包含一个分支的深度。顺着根节点往下走只要某个节点只有一个孩子就说明所有字符串在这个位置上的字符依然一致可以把这个字符加入答案一旦遇到分支节点或叶子节点就停止。class TrieNode: def __init__(self): self.children {} self.is_end False def longest_common_prefix_trie(strs: list[str]) - str: if not strs: return root TrieNode() for s in strs: node root for ch in s: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True result [] node root while len(node.children) 1 and not node.is_end: ch next(iter(node.children)) result.append(ch) node node.children[ch] return .join(result)循环终止条件包含not node.is_end是个关键细节。如果某个字符串本身就是另一个字符串的前缀比如数组是[ab, a]根节点下的路径在字符a处已经是一个字符串的终点此时虽然只有一个孩子也不能继续往下走了因为再往下取的b并不是所有字符串的公共前缀。3.2 字典树的工程价值与空间成本字典树在纯算法题里并不是最短的解法但它有一个其他解法都没有的特性建好树之后任何新的字符串进来都可以在 O(m) 时间内判断它和全体数据的最长公共前缀。横向扫描和纵向扫描每次都要从头跑一遍而字典树支持重复查询。代价是空间。每个节点都存一个哈希表存储开销远高于数组本身。在实际工程中如果字符串集合是一次性构建、后续查询很少字典树不一定划算但如果要做批量前缀匹配、自动补全、IP 路由表最长前缀匹配这类任务字典树几乎是最标准的答案。面试时候选人可以提一句空间换时间适合查询多、写入少的场景。这比单纯背一道题更能体现对数据结构本质的理解。4. 边界条件测试与常见错误排查4.1 边界用例速查表这道题的正确性很大程度上取决于边界处理我整理了一张常见测试用例表建议写代码时逐条对照跑一遍。输入期望输出说明[]空数组所有解法都必须在入口处拦截[]只有一个空串最短长度就是 0[abc]abc只有一个字符串公共前缀就是它本身[abc, abc, abc]abc所有字符串完全相同[ab, a]a某个字符串是另一个的前缀[a, ab, abc]a最短字符串本身就是公共前缀[racecar, car]首字符都不相同[, abc]只要有一个空串公共前缀必为空4.2 新手最容易踩的四个坑第一个坑是忘记空数组判断。很多横向扫描代码一开始就直接prefix strs[0]输入为空时立刻抛异常面试现场写法上直接失分。第二个坑是外层循环长度选错。纵向扫描里如果以最短字符串长度为基准确实也能工作但必须额外求一次最短长度而直接以第一个字符串长度为基准更简单内层再通过i len(s)做越界保护逻辑反而更统一。第三个坑是二分查找死循环。前面已经提过向上取整的问题这是二分求右边界时最高频的失误。如果没意识到这一点调试时很难发现为什么程序一直卡在某个长度上。第四个坑是过早返回导致误判。分治法合并时如果左右两边的公共前缀求得正确合并不太容易出错但横向扫描里如果拿了strs[0]和strs[-1]直接算公共前缀就忽略了中国字符串结果必然错误。这个反例在面试追问里经常出现建议自己心里有个谱。4.3 多语言实现差异提示Python 写起来最顺手但字符串不可变频繁切片会有复制开销纵向扫描直接比较字符索引的写法通常是最省内存的。用 Go 写横向扫描时a[:i]切片是引用底层数组的不会像 Python 那样立即复制这让切片操作成本远低于 Python但要注意切片持有的底层数组可能导致内存无法释放长期运行的场景用string(a[:i])或先收集字节再转换更稳妥。Java 里substring在较新版本中也是复制字符数组的大规模数据下尽量用StringBuilder逐步构建前缀避免频繁创建中间字符串。5. 复杂度计算分析与工程化思考5.1 时间复杂度推导过程设字符串数量为 n最短字符串长度为 m所有字符串总长度为 S。横向扫描每轮都在缩短当前候选前缀最坏情况下所有字符串内容完全一致每轮都要把当前前缀完整比一遍复杂度就是前缀长度 n 次累加也就是 O(S)。纵向扫描最坏情况同样要比较每个字符串的每个字符也是 O(S)。分治法的每一层合并操作本质上也是在不重复或少量重复的情况下扫描字符整体依然控制在 O(S)。二分查找每轮都要对所有字符串调用一次startswith检查每轮检查成本是 O(n * mid)总共 log m 轮所以是 O(n * m * log m)也就是 O(S log m)。字典树建树的插入成本是 O(S)查询公共前缀时遍历深度最多为 m所以是 O(S m)。解法最坏时间复杂度额外空间是否支持流式输入横向扫描O(S)O(1)不支持依赖第一个字符串做初始值纵向扫描O(S)O(1)部分支持逐列检查天然适合逐行读取分治法O(S)O(m log n)不支持需要完整数组分片二分查找O(S log m)O(1)不支持需要最短长度字典树O(S m)O(S)支持可以边插入边查询5.2 从算法题延伸到真实系统设计公共前缀计算并不只是刷题用。比如在一个日志分析系统里需要从几十万条 SQL 语句中统计共同的查询前缀找出模式化访问的流量特征又比如在做批量文件同步时要计算所有文件路径的最长公共目录决定从哪里开始打包再比如网络设备做路由聚合时IP 前缀的最长匹配本质上就是公共前缀问题在二进制空间里的变体。我见过一个真实案例某团队要在一批序列化数据里提取冗余字段路径数据量很大字符串长度平均几百字节。他们最初用横向扫描因为大多数记录在第二个字段位就出现差异整体表现还好。后来数据源格式变了很多记录共享了非常长的前半段横向扫描的耗时立刻上升。替换成二分查找后查询次数从“逐字符扩散”变成“按长度跳跃”在共享前缀很长、整体数据量大的场景下提速非常明显。这说明同一个算法在不同数据特征下会有完全不同的表现理解数据形态比背时间复杂度更重要。5.3 面试追问与思路升华面试官在这道题上最常见的追问是如果字符串数量巨大内存放不下怎么办这个问题可以这样回答逐列扫描天然支持流式读取每次只比较一个字符不需要把所有字符串一次性载入内存。字典树虽然查询能力强但构建时需要访问全部数据流式场景反而不好做。所以“数据规模”和“内存上限”会直接决定你选择哪个方案。另一个追问是如果求的不是单个字符串数组的公共前缀而是动态追加新字符串时要实时维护公共前缀你会怎么设计这时候可以用字典树思想维护一个计数器每个节点记录经过该节点的字符串数量当已有 N 个字符串时如果当前节点计数等于 N则说明该字符对所有字符串都出现可以计入公共前缀一旦计数小于 N就停止。这种扩展设计说明你不只是背了一个模板而是真的理解了公共前缀的数据结构本质。6. 写在最后这道题我刷过不止一遍每次重做都有新体会。早期我只追求“AC”后来开始对比不同解法在极端输入下的表现再后来把它搬到了分布式日志解析的场景里才发现算法题和工程实践之间的连接点其实比想象中多得多。个人经验是如果时间紧迫优先把纵向扫描写得滚瓜烂熟它代码短、边界意识强、不需要额外空间适合作为面试时的默认答案。如果聊到优化再引出二分查找或字典树这会显得你的知识是有层次的而不是一味堆解法。最后一个小技巧写完后用前面那张边界用例表过一遍尤其是[, abc]和[ab, a]这两条能防住绝大多数隐藏 bug。