1. 初识最长公共前缀题目拆解与出题人意图1.1 从一道入门题看后端面试的考察逻辑最长公共前缀在LeetCode上的序号是14难度标注为Easy。但如果你在面试中把它当成一道“送分题”来对待那可能就踩进了出题人精心设计的陷阱里。这道题表面问的是“找公共前缀”实际考察的却是三样东西第一你能不能快速给出一个正确解法第二你能不能在有提示的情况下想到更优的思路第三你在边界条件的处理上是不是足够细腻。说白了这是一道“一看就会一写就错”的典型题目。我自己面过不少候选人简历上写着“熟悉常见算法”结果让手写这道题能一次写对的人不到三分之一。大多数人的问题不是“不会做”而是“考虑得太少”——空字符串怎么办、只有一个字符串怎么办、公共前缀是完整字符串怎么办、大小写是否敏感、是否有Unicode字符……这些细节一个接一个地抛出来很多人的代码当场就崩了。这道题适合谁来学一是准备春招秋招的应届生二是想转岗后端开发但算法基础不牢的社招选手三是刷了题但总觉得自己“背答案”而不是“懂思路”的人。它的价值不在题目本身而在于它足够简单、足够经典能把算法思维的几个核心要素串起来。1.2 边界条件才是这道题真正的“考点”先看题目原意给定一个字符串数组找出所有字符串共同的最长公共前缀如果不存在则返回空字符串。听起来毫无难度是吧但你把下面这几个case跑一遍就知道自己是不是真的想清楚了输入[flower,flow,flight]输出fl。输入[dog,racecar,car]输出。输入[]输出。输入[]输出。输入[a]输出a。最后一个case我特意标出来了因为真的有不少人挂在它上面。他们的代码逻辑是“拿第一个字符串当基准然后依次和后面的字符串比较”但算法从头到尾只处理了一个字符串于是有人直接返回了空串有人报了数组越界还有人干脆死循环了。为什么会这样因为很多人在动手写之前没有把“公共前缀的最短长度一定小于等于所有字符串中最短的那个”这条隐含约束在代码里体现出来。这个问题往后走到纵向扫描和二分法里还会再次出现所以我在带人的时候第一句话永远是先把边界条件想清楚再写主体逻辑。2. 暴力美学的正确打开方式横向扫描全解析2.1 暴力解法不是简单粗暴而是最小可行思路“算法的暴力美学”这个词是我当年和一个同事闲聊时冒出来的。当时他在看一个实习生写的代码那个实习生没有用任何花哨的数据结构就是用两层循环硬刚结果代码短、运行快、可读性还特别好。同事感慨了一句有时候暴力就是美。暴力的本质是什么是“最小可行思路”——你先不管效率直接按照题目的定义去模拟操作。最长公共前缀的暴力做法就是横向扫描从第一个字符串开始把它的前缀和第二个字符串比对得到这两个字符串的公共前缀再拿这个结果和第三个字符串比对依次类推。这种思路和一个人手工做这道题的过程完全一致理解成本几乎为零。别小看这件事在面试高压环境下能稳定地交出一份“完全正确”的暴力解已经比一半候选人强了。我为什么说“稳定”很重要因为面试官不会只judge你的最终答案他更关注你的整个思考链路。你写暴力解的过程展示的是我能理解题意、我能给出正确实现、我能分析复杂度。这些都是加分项。有些候选人一上来就憋二分法结果卡了二十分钟写不出来最后连最简单的解都拿不出手这才是真正的扣分项。2.2 一步一步拆实现代码与执行过程对照横向扫描的代码大抵长这样def longest_common_prefix(strs): if not strs: return prefix strs[0] for s in strs[1:]: # 只要 s 不是以 prefix 开头就不断剪短 prefix while not s.startswith(prefix): prefix prefix[:-1] if not prefix: return return prefix这段代码的过程可以这么理解假设输入是[flower, flow, flight]第一步prefix初始化为flower。第二步用flow去比对它不以flower开头于是prefix剪短为flowe还是不满足继续剪到flow时匹配成功于是公共前缀变成flow。第三步用flight去比对flight不以flow开头剪成flo不行再剪成fl此时匹配成功循环结束返回fl。这个实现的精妙之处在于它没有显式地去“找”公共前缀而是用了“剪短”的思路。每次比对失败就丢掉当前前缀的最后一个字符直到和当前字符串对得上。这其实就是“从最长可能的情况出发逐步缩小范围”的思想很多其他算法里也能看到它的影子比如最长公共子序列的状态转移。复杂度方面设字符串数组长度为 n字符串平均长度为 m最坏情况下外层循环 n 次、每次内层最多剪 m 次每次startswith判断又需要 O(m) 的时间所以整体最坏是 O(n * m^2)。咦这里有人可能会问为什么不是 O(n * m)因为“判断 剪短”这两个操作是叠加的每次剪短后都要重新做一次前缀匹配最坏情况是一个长字符串和另一个几乎相同的长字符串比较比如aaaaab和aaaaaa你可能要剪五次、比六次。这个复杂度在实际面试中一定要能算清楚因为面试官一定会追问。空间复杂度就非常漂亮了只有prefix这一个额外变量O(1)。2.3 复杂度分析与“暴力但稳”的状态“暴力但稳”这四个字是我对这道题横向扫描解法的最真实评价。它的缺点很明显如果数组中所有字符串都很长、数量很多那么重复的startswith判断会带来不必要的开销。在极端输入下比如一万个长度为一百万的字符串这个思路的耗时会让LeetCode给你一个红色的“Time Limit Exceeded”。但好在LeetCode的测试数据没有这么丧心病狂横向扫描在实际测试里跑得还挺快。我记得它在LeetCode上的运行时间大概是32ms左右击败了八成以上的提交。这说明了什么很多时候所谓“最优解”和“暴力解”在工程实际上差距没有想象中大反而越简单的代码越不容易出错、越容易维护。所以在面试时我的建议很明确你先写横向扫描清楚地解释它的正确性和复杂度这叫“保底”。然后如果面试官追问“能不能优化一下”你再引出纵向扫描、分治、二分这些思路。这个过程展示的就是从暴力到优化的完整思维链比一上来就炫技要讨喜得多。3. 从暴力到优雅四种主流解法横向对比3.1 纵向扫描字母列的思维方式纵向扫描的思路和横向扫描完全不同。横向是“按字符串看”而纵向是“按字符看”。具体来说就是拿第一个字符串的第 0 位字符去和其他所有字符串的第 0 位字符比然后再拿第 1 位去比依次类推直到遇到某个字符串的字符对不上或者某个字符串提前结束了就直接返回当前位置之前的子串。def longest_common_prefix(strs): if not strs: return for i in range(len(strs[0])): char strs[0][i] for s in strs[1:]: if i len(s) or s[i] ! char: return strs[0][:i] return strs[0]纵向扫描的优势在“大多数时候”它在遇到第一个不一致的字符后立刻返回不会像横向扫描那样反复剪短一个已经接近答案的前缀。最坏复杂度是 O(n * m)比横向扫描的 O(n * m^2) 要省一个数量级。实际提交到LeetCode运行时间大约是 24ms。我在写代码的时候特意加了一条i len(s)的判断这一步极其关键。如果不加当某个字符串比第一个字符串短而你又正好访问到它不存在的索引时Python会直接抛IndexError。这就是我在第一节说的“边界条件才是真正的考点”。3.2 分治与二分不同代价下的优化路线分治法的思路是把数组从中间切成两半分别求出左半部分所有字符串的最长公共前缀、右半部分所有字符串的最长公共前缀然后再求这两个前缀的公共前缀。递归的过程很像归并排序def longest_common_prefix(strs): if not strs: return return divide_conquer(strs, 0, len(strs) - 1) def divide_conquer(strs, left, right): if left right: return strs[left] mid (left right) // 2 left_prefix divide_conquer(strs, left, mid) right_prefix divide_conquer(strs, mid 1, right) return common_between(left_prefix, right_prefix) def common_between(s1, s2): min_len min(len(s1), len(s2)) i 0 while i min_len and s1[i] s2[i]: i 1 return s1[:i]分治的时间复杂度是 O(n * m)和纵向扫描一致但它看起来“高级”很多。面试官看到你写分治大概率会眼前一亮因为这至少说明你熟悉递归结构和“将问题拆成子问题再合并”的套路。不过分治有一个小代价递归会使用调用栈在极端情况下数组特别大有栈溢出的风险虽然实际不太可能遇到。二分法的思路则更加微妙既然公共前缀的长度一定在 0 和 min_len(所有字符串的最短长度) 之间那么可以直接二分这个长度。每猜一个长度 mid就检查所有字符串的前 mid 个字符是否相等相等就往长了猜不相等就往短了猜。这种“猜答案再验证”的思想在很多算法题里都出现过比如在有序数组里找某个值对应的下标范围。def longest_common_prefix(strs): if not strs: return min_len min(len(s) for s in strs) low, high 0, min_len while low high: mid (low high 1) // 2 prefix strs[0][:mid] if all(s.startswith(prefix) for s in strs): low mid else: high mid - 1 return strs[0][:low]这里求 mid 用的是(low high 1) // 2也就是“上取整”。为什么要这样因为当 low 和 high 只差 1 时如果直接用(low high) // 2mid 会等于 low若此时验证成功low 更新为 mid等于没变循环就死循环了。这个问题在二分查找的变体题里特别常见我当年第一次写的时候也踩过这个坑。二分法的时间复杂度同样是 O(n * m * log(m))因为二分需要 log(m) 轮每轮都要对整个数组做一次前缀判断。从这个角度看二分法在复杂度上并不占优它更大的价值在于“让面试官看到你掌握了二分这个工具”以及你对“答案具有单调性”这个隐含机制的敏感度。3.3 解法选型对照表面试该用哪一种我把四种解法放在一起做了个表方便你在面试时快速决策解法时间复杂度空间复杂度代码量面试推荐指数横向扫描O(n * m^2)O(1)很少三星保底首选纵向扫描O(n * m)O(1)很少四星均衡首选分治法O(n * m)O(log n) 递归栈中等四星展现功力二分法O(n * m * log m)O(1)中等三星加分但非必需我的实际建议是面试时先用纵向扫描打底因为它的代码最短、思路最直观、复杂度也说得过去。如果面试官问“还能怎么优化”你再抛出分治法顺便讲讲你如何把一个大问题拆成左右两个子问题。至于二分法可以作为“额外彩蛋”。注意不要让这个彩蛋喧宾夺主毕竟算法面试考察的是沟通和思维的过程不是谁背的解法多。4. 面试实战一题多解如何帮你把Offer聊到手4.1 从暴力到优化的“表演路径”面试的时候你展示的不应该只是一个最终答案而是一整套“发现问题和优化问题”的能力。我建议的路径是这样的第一步画两个示例把数组画成一列竖排的字符串拿笔画出公共前缀的位置。这个动作看起来浪费时间但能让面试官看到你在“理解题意”而不是背答案。第二步口头描述暴力思路。不要上来就写代码先说“我打算拿第一个字符串当基准然后逐个和后面的字符串比对如果不匹配就不断缩短当前前缀直到找到所有字符串共有的部分”。这段话一说出口你的思路就已经被面试官理解了。第三步分析复杂度。说清楚 O(n * m^2) 是怎么来的然后主动提一句“这个复杂度在最坏情况下偏高我能不能优化一下”。第四步在面试官点头后按我刚才写的纵向扫描代码边写边注释解释每个判断分支在防什么边界情况。这套流程走下来面试官心里对你的评价往往比“这个人用了最优解”要高得多。因为前者展示的是“我能思考”后者只展示“我见过这道题”。4.2 容易被追问的细节字符串不可变与内存分配这道题有一个隐藏的面试坑那就是Python的字符串是不可变对象。每次执行prefix prefix[:-1]Python都会创建一个新的字符串对象然后把prefix指向新对象旧对象等待垃圾回收。在横向扫描里如果最长公共前缀很短而字符串又特别长那么剪短的过程就会产生大量临时字符串GC的压力会急剧上升。这个问题在C或Java里则需要换个说法。C用string其实也存在类似的拷贝问题Java则因为String不可变有一样的情况。面试官如果问你“这个代码在极端输入下有什么性能隐患”十有八九就是在等你答这一点。应对的思路有两个方向一是改用纵向扫描它只做字符比较不创建中间字符串二是如果必须用横向扫描可以用可变数据结构比如Java的StringBuilder或C的string来避免反复创建新对象。这种追问往往发生在“你觉得你写完了吗”之后属于面试官故意留出来的“加分题”。4.3 常见错误与调试实录我统计了一下候选人在这道题上翻车的几个典型位置基本是下面这几个。排名第一的坑是strs为空数组时直接访问strs[0]抛出IndexError。这个最容易发生在“看题目简单直接开写”的候选人身上。解法就一行if not strs: return 但你必须在任何逻辑之前写上它。排名第二的坑是只有一个字符串时循环直接跳过返回了空串而不是原字符串。很多人的失败不是逻辑大错而是没想清楚“单个字符串的公共前缀就是它自己”这个约定。在横向扫描的实现里只要prefix初始化为strs[0]这个case就天然正确。排名第三的坑是没有处理“公共前缀不存在”的情况。比如[dog,racecar,car]第一轮比较就失败应该返回空字符串。有些人在这里返回了None而题目要求返回虽然语义上接近但测试用例会判定你错。返回值的约束也要注意。把这三个坑都填上你的代码鲁棒性就已经超过大多数人了。我面试别人的时候看到候选人能主动提一句话“我先处理几个边界情况”基本上心里就已经给这个人打了“通过”的标记。5. 举一反三公共前缀思想在业务代码中的延伸5.1 从算法题到业务逻辑前缀匹配的实用场景很多人刷算法题的时候觉得很虚觉得这些题和日常工作没什么关系。但最长公共前缀的思路在真实业务场景里其实非常常见。举个例子你在做对象存储或者分布式文件系统的时候需要把大批文件URL按照目录层级做聚合这时候“求这些URL的公共前缀”就决定了你能从哪个根目录开始聚合也决定了缓存分层的key怎么设计。再比如在代码编辑器里做关键字自动补全的时候你输入了long_common_pr编辑器需要拿着这个前缀去索引里匹配所有候选词。这个过程本质上就是一个“前缀匹配”的过程只是它比求公共前缀更宽松——是“一个字符串是否是另一个的前缀”而不是“一堆字符串的公共前缀”。还有字符串排序之后的相邻比较也能用到公共前缀的思想。这个点我不是瞎说的LeetCode上有一道题叫“最长公共前缀”的变体解题思路是先对所有字符串排序然后只比较排完序后的第一个和最后一个字符串它们的公共前缀就是整个数组的公共前缀。这个trick的巧妙之处在于排序后字典序最小的和字典序最大的把其他所有字符串“夹”在中间公共前缀必须同时是这两个来决定因为它是两者字典序差异最小的边界。我当年在一个日志分析项目里用过类似的思路。当时的日志文件里有很多重复前缀的路径比如/api/v1/user/profile、/api/v1/user/avatar、/api/v1/user/password我想把它们在统计面板里聚合到/api/v1/user这个层级。用排序后首尾比较的方法一行逻辑就搞定了性能也非常好。5.2 与Trie树、排序等知识的联动讲到前缀不得不提的就是字典树Trie。Trie树的核心能力就是按前缀组织词汇它的插入过程和查询过程都是围绕“检查下一个字符是否存在”展开的。最长公共前缀这道题如果你把所有字符串插入一棵Trie树然后从根节点往下走走到第一个“分叉”的地方那么从根到分叉点这段路径就是所有字符串的最长公共前缀。这种思路的优雅之处在于它把“对多个字符串求公共前缀”的问题转换成了“在Trie树上找最早出现分支的节点”的问题。面试的时候如果你能主动提到这种关联即使你不写完整Trie实现面试官也会认为你对数据结构的理解是成体系的而不是一个一个孤立的知识点。有向无环图和并发前缀匹配也有类似思想比如HTTP路由的分段匹配、数据库索引的复合前缀匹配都属于“前缀”这一概念的变体。学会了这个基础你去看很多框架的源码会突然觉得容易理解很多。5.3 一套“从看懂到会写”的刷题心法最后分享一个我自己的刷题套路对最长公共前缀这种“中等偏简单”的题特别好用。第一步把题目的所有边界条件自己列出来然后带着这些边界条件去读示例。第二步用人话描述你的暴力解法把它说给一个虚拟的同事听看他说不说得通。第三步先写正确但耗时的解法跑通所有测试用例再思考怎么优化。第四步优化之后不急着提交写几个“畸形输入”测试一下空数组、单个元素、全同字符串、完全无公共前缀、超长字符串和短字符串的混搭。这个流程看着慢但练下来之后你会发现笔试和面试的能力提升效率远超直接刷题。刷题不是比谁刷得多而是比谁能从一道题里抽取到一套可复用的思维工具。最长公共前缀这个工具里面塞进了边界处理、复杂度计算、多方案选型、从暴力到优化的跃迁路径四个全占了。我个人带实习生的经验是把一个核心概念嚼透胜过囫囵吞枣地刷三五十道题。毕竟面试官不傻真正有没有理解三言两语就能试出来。 最长公共前缀算法解析：从暴力扫描到分治二分的面试进阶指南
1. 初识最长公共前缀题目拆解与出题人意图1.1 从一道入门题看后端面试的考察逻辑最长公共前缀在LeetCode上的序号是14难度标注为Easy。但如果你在面试中把它当成一道“送分题”来对待那可能就踩进了出题人精心设计的陷阱里。这道题表面问的是“找公共前缀”实际考察的却是三样东西第一你能不能快速给出一个正确解法第二你能不能在有提示的情况下想到更优的思路第三你在边界条件的处理上是不是足够细腻。说白了这是一道“一看就会一写就错”的典型题目。我自己面过不少候选人简历上写着“熟悉常见算法”结果让手写这道题能一次写对的人不到三分之一。大多数人的问题不是“不会做”而是“考虑得太少”——空字符串怎么办、只有一个字符串怎么办、公共前缀是完整字符串怎么办、大小写是否敏感、是否有Unicode字符……这些细节一个接一个地抛出来很多人的代码当场就崩了。这道题适合谁来学一是准备春招秋招的应届生二是想转岗后端开发但算法基础不牢的社招选手三是刷了题但总觉得自己“背答案”而不是“懂思路”的人。它的价值不在题目本身而在于它足够简单、足够经典能把算法思维的几个核心要素串起来。1.2 边界条件才是这道题真正的“考点”先看题目原意给定一个字符串数组找出所有字符串共同的最长公共前缀如果不存在则返回空字符串。听起来毫无难度是吧但你把下面这几个case跑一遍就知道自己是不是真的想清楚了输入[flower,flow,flight]输出fl。输入[dog,racecar,car]输出。输入[]输出。输入[]输出。输入[a]输出a。最后一个case我特意标出来了因为真的有不少人挂在它上面。他们的代码逻辑是“拿第一个字符串当基准然后依次和后面的字符串比较”但算法从头到尾只处理了一个字符串于是有人直接返回了空串有人报了数组越界还有人干脆死循环了。为什么会这样因为很多人在动手写之前没有把“公共前缀的最短长度一定小于等于所有字符串中最短的那个”这条隐含约束在代码里体现出来。这个问题往后走到纵向扫描和二分法里还会再次出现所以我在带人的时候第一句话永远是先把边界条件想清楚再写主体逻辑。2. 暴力美学的正确打开方式横向扫描全解析2.1 暴力解法不是简单粗暴而是最小可行思路“算法的暴力美学”这个词是我当年和一个同事闲聊时冒出来的。当时他在看一个实习生写的代码那个实习生没有用任何花哨的数据结构就是用两层循环硬刚结果代码短、运行快、可读性还特别好。同事感慨了一句有时候暴力就是美。暴力的本质是什么是“最小可行思路”——你先不管效率直接按照题目的定义去模拟操作。最长公共前缀的暴力做法就是横向扫描从第一个字符串开始把它的前缀和第二个字符串比对得到这两个字符串的公共前缀再拿这个结果和第三个字符串比对依次类推。这种思路和一个人手工做这道题的过程完全一致理解成本几乎为零。别小看这件事在面试高压环境下能稳定地交出一份“完全正确”的暴力解已经比一半候选人强了。我为什么说“稳定”很重要因为面试官不会只judge你的最终答案他更关注你的整个思考链路。你写暴力解的过程展示的是我能理解题意、我能给出正确实现、我能分析复杂度。这些都是加分项。有些候选人一上来就憋二分法结果卡了二十分钟写不出来最后连最简单的解都拿不出手这才是真正的扣分项。2.2 一步一步拆实现代码与执行过程对照横向扫描的代码大抵长这样def longest_common_prefix(strs): if not strs: return prefix strs[0] for s in strs[1:]: # 只要 s 不是以 prefix 开头就不断剪短 prefix while not s.startswith(prefix): prefix prefix[:-1] if not prefix: return return prefix这段代码的过程可以这么理解假设输入是[flower, flow, flight]第一步prefix初始化为flower。第二步用flow去比对它不以flower开头于是prefix剪短为flowe还是不满足继续剪到flow时匹配成功于是公共前缀变成flow。第三步用flight去比对flight不以flow开头剪成flo不行再剪成fl此时匹配成功循环结束返回fl。这个实现的精妙之处在于它没有显式地去“找”公共前缀而是用了“剪短”的思路。每次比对失败就丢掉当前前缀的最后一个字符直到和当前字符串对得上。这其实就是“从最长可能的情况出发逐步缩小范围”的思想很多其他算法里也能看到它的影子比如最长公共子序列的状态转移。复杂度方面设字符串数组长度为 n字符串平均长度为 m最坏情况下外层循环 n 次、每次内层最多剪 m 次每次startswith判断又需要 O(m) 的时间所以整体最坏是 O(n * m^2)。咦这里有人可能会问为什么不是 O(n * m)因为“判断 剪短”这两个操作是叠加的每次剪短后都要重新做一次前缀匹配最坏情况是一个长字符串和另一个几乎相同的长字符串比较比如aaaaab和aaaaaa你可能要剪五次、比六次。这个复杂度在实际面试中一定要能算清楚因为面试官一定会追问。空间复杂度就非常漂亮了只有prefix这一个额外变量O(1)。2.3 复杂度分析与“暴力但稳”的状态“暴力但稳”这四个字是我对这道题横向扫描解法的最真实评价。它的缺点很明显如果数组中所有字符串都很长、数量很多那么重复的startswith判断会带来不必要的开销。在极端输入下比如一万个长度为一百万的字符串这个思路的耗时会让LeetCode给你一个红色的“Time Limit Exceeded”。但好在LeetCode的测试数据没有这么丧心病狂横向扫描在实际测试里跑得还挺快。我记得它在LeetCode上的运行时间大概是32ms左右击败了八成以上的提交。这说明了什么很多时候所谓“最优解”和“暴力解”在工程实际上差距没有想象中大反而越简单的代码越不容易出错、越容易维护。所以在面试时我的建议很明确你先写横向扫描清楚地解释它的正确性和复杂度这叫“保底”。然后如果面试官追问“能不能优化一下”你再引出纵向扫描、分治、二分这些思路。这个过程展示的就是从暴力到优化的完整思维链比一上来就炫技要讨喜得多。3. 从暴力到优雅四种主流解法横向对比3.1 纵向扫描字母列的思维方式纵向扫描的思路和横向扫描完全不同。横向是“按字符串看”而纵向是“按字符看”。具体来说就是拿第一个字符串的第 0 位字符去和其他所有字符串的第 0 位字符比然后再拿第 1 位去比依次类推直到遇到某个字符串的字符对不上或者某个字符串提前结束了就直接返回当前位置之前的子串。def longest_common_prefix(strs): if not strs: return for i in range(len(strs[0])): char strs[0][i] for s in strs[1:]: if i len(s) or s[i] ! char: return strs[0][:i] return strs[0]纵向扫描的优势在“大多数时候”它在遇到第一个不一致的字符后立刻返回不会像横向扫描那样反复剪短一个已经接近答案的前缀。最坏复杂度是 O(n * m)比横向扫描的 O(n * m^2) 要省一个数量级。实际提交到LeetCode运行时间大约是 24ms。我在写代码的时候特意加了一条i len(s)的判断这一步极其关键。如果不加当某个字符串比第一个字符串短而你又正好访问到它不存在的索引时Python会直接抛IndexError。这就是我在第一节说的“边界条件才是真正的考点”。3.2 分治与二分不同代价下的优化路线分治法的思路是把数组从中间切成两半分别求出左半部分所有字符串的最长公共前缀、右半部分所有字符串的最长公共前缀然后再求这两个前缀的公共前缀。递归的过程很像归并排序def longest_common_prefix(strs): if not strs: return return divide_conquer(strs, 0, len(strs) - 1) def divide_conquer(strs, left, right): if left right: return strs[left] mid (left right) // 2 left_prefix divide_conquer(strs, left, mid) right_prefix divide_conquer(strs, mid 1, right) return common_between(left_prefix, right_prefix) def common_between(s1, s2): min_len min(len(s1), len(s2)) i 0 while i min_len and s1[i] s2[i]: i 1 return s1[:i]分治的时间复杂度是 O(n * m)和纵向扫描一致但它看起来“高级”很多。面试官看到你写分治大概率会眼前一亮因为这至少说明你熟悉递归结构和“将问题拆成子问题再合并”的套路。不过分治有一个小代价递归会使用调用栈在极端情况下数组特别大有栈溢出的风险虽然实际不太可能遇到。二分法的思路则更加微妙既然公共前缀的长度一定在 0 和 min_len(所有字符串的最短长度) 之间那么可以直接二分这个长度。每猜一个长度 mid就检查所有字符串的前 mid 个字符是否相等相等就往长了猜不相等就往短了猜。这种“猜答案再验证”的思想在很多算法题里都出现过比如在有序数组里找某个值对应的下标范围。def longest_common_prefix(strs): if not strs: return min_len min(len(s) for s in strs) low, high 0, min_len while low high: mid (low high 1) // 2 prefix strs[0][:mid] if all(s.startswith(prefix) for s in strs): low mid else: high mid - 1 return strs[0][:low]这里求 mid 用的是(low high 1) // 2也就是“上取整”。为什么要这样因为当 low 和 high 只差 1 时如果直接用(low high) // 2mid 会等于 low若此时验证成功low 更新为 mid等于没变循环就死循环了。这个问题在二分查找的变体题里特别常见我当年第一次写的时候也踩过这个坑。二分法的时间复杂度同样是 O(n * m * log(m))因为二分需要 log(m) 轮每轮都要对整个数组做一次前缀判断。从这个角度看二分法在复杂度上并不占优它更大的价值在于“让面试官看到你掌握了二分这个工具”以及你对“答案具有单调性”这个隐含机制的敏感度。3.3 解法选型对照表面试该用哪一种我把四种解法放在一起做了个表方便你在面试时快速决策解法时间复杂度空间复杂度代码量面试推荐指数横向扫描O(n * m^2)O(1)很少三星保底首选纵向扫描O(n * m)O(1)很少四星均衡首选分治法O(n * m)O(log n) 递归栈中等四星展现功力二分法O(n * m * log m)O(1)中等三星加分但非必需我的实际建议是面试时先用纵向扫描打底因为它的代码最短、思路最直观、复杂度也说得过去。如果面试官问“还能怎么优化”你再抛出分治法顺便讲讲你如何把一个大问题拆成左右两个子问题。至于二分法可以作为“额外彩蛋”。注意不要让这个彩蛋喧宾夺主毕竟算法面试考察的是沟通和思维的过程不是谁背的解法多。4. 面试实战一题多解如何帮你把Offer聊到手4.1 从暴力到优化的“表演路径”面试的时候你展示的不应该只是一个最终答案而是一整套“发现问题和优化问题”的能力。我建议的路径是这样的第一步画两个示例把数组画成一列竖排的字符串拿笔画出公共前缀的位置。这个动作看起来浪费时间但能让面试官看到你在“理解题意”而不是背答案。第二步口头描述暴力思路。不要上来就写代码先说“我打算拿第一个字符串当基准然后逐个和后面的字符串比对如果不匹配就不断缩短当前前缀直到找到所有字符串共有的部分”。这段话一说出口你的思路就已经被面试官理解了。第三步分析复杂度。说清楚 O(n * m^2) 是怎么来的然后主动提一句“这个复杂度在最坏情况下偏高我能不能优化一下”。第四步在面试官点头后按我刚才写的纵向扫描代码边写边注释解释每个判断分支在防什么边界情况。这套流程走下来面试官心里对你的评价往往比“这个人用了最优解”要高得多。因为前者展示的是“我能思考”后者只展示“我见过这道题”。4.2 容易被追问的细节字符串不可变与内存分配这道题有一个隐藏的面试坑那就是Python的字符串是不可变对象。每次执行prefix prefix[:-1]Python都会创建一个新的字符串对象然后把prefix指向新对象旧对象等待垃圾回收。在横向扫描里如果最长公共前缀很短而字符串又特别长那么剪短的过程就会产生大量临时字符串GC的压力会急剧上升。这个问题在C或Java里则需要换个说法。C用string其实也存在类似的拷贝问题Java则因为String不可变有一样的情况。面试官如果问你“这个代码在极端输入下有什么性能隐患”十有八九就是在等你答这一点。应对的思路有两个方向一是改用纵向扫描它只做字符比较不创建中间字符串二是如果必须用横向扫描可以用可变数据结构比如Java的StringBuilder或C的string来避免反复创建新对象。这种追问往往发生在“你觉得你写完了吗”之后属于面试官故意留出来的“加分题”。4.3 常见错误与调试实录我统计了一下候选人在这道题上翻车的几个典型位置基本是下面这几个。排名第一的坑是strs为空数组时直接访问strs[0]抛出IndexError。这个最容易发生在“看题目简单直接开写”的候选人身上。解法就一行if not strs: return 但你必须在任何逻辑之前写上它。排名第二的坑是只有一个字符串时循环直接跳过返回了空串而不是原字符串。很多人的失败不是逻辑大错而是没想清楚“单个字符串的公共前缀就是它自己”这个约定。在横向扫描的实现里只要prefix初始化为strs[0]这个case就天然正确。排名第三的坑是没有处理“公共前缀不存在”的情况。比如[dog,racecar,car]第一轮比较就失败应该返回空字符串。有些人在这里返回了None而题目要求返回虽然语义上接近但测试用例会判定你错。返回值的约束也要注意。把这三个坑都填上你的代码鲁棒性就已经超过大多数人了。我面试别人的时候看到候选人能主动提一句话“我先处理几个边界情况”基本上心里就已经给这个人打了“通过”的标记。5. 举一反三公共前缀思想在业务代码中的延伸5.1 从算法题到业务逻辑前缀匹配的实用场景很多人刷算法题的时候觉得很虚觉得这些题和日常工作没什么关系。但最长公共前缀的思路在真实业务场景里其实非常常见。举个例子你在做对象存储或者分布式文件系统的时候需要把大批文件URL按照目录层级做聚合这时候“求这些URL的公共前缀”就决定了你能从哪个根目录开始聚合也决定了缓存分层的key怎么设计。再比如在代码编辑器里做关键字自动补全的时候你输入了long_common_pr编辑器需要拿着这个前缀去索引里匹配所有候选词。这个过程本质上就是一个“前缀匹配”的过程只是它比求公共前缀更宽松——是“一个字符串是否是另一个的前缀”而不是“一堆字符串的公共前缀”。还有字符串排序之后的相邻比较也能用到公共前缀的思想。这个点我不是瞎说的LeetCode上有一道题叫“最长公共前缀”的变体解题思路是先对所有字符串排序然后只比较排完序后的第一个和最后一个字符串它们的公共前缀就是整个数组的公共前缀。这个trick的巧妙之处在于排序后字典序最小的和字典序最大的把其他所有字符串“夹”在中间公共前缀必须同时是这两个来决定因为它是两者字典序差异最小的边界。我当年在一个日志分析项目里用过类似的思路。当时的日志文件里有很多重复前缀的路径比如/api/v1/user/profile、/api/v1/user/avatar、/api/v1/user/password我想把它们在统计面板里聚合到/api/v1/user这个层级。用排序后首尾比较的方法一行逻辑就搞定了性能也非常好。5.2 与Trie树、排序等知识的联动讲到前缀不得不提的就是字典树Trie。Trie树的核心能力就是按前缀组织词汇它的插入过程和查询过程都是围绕“检查下一个字符是否存在”展开的。最长公共前缀这道题如果你把所有字符串插入一棵Trie树然后从根节点往下走走到第一个“分叉”的地方那么从根到分叉点这段路径就是所有字符串的最长公共前缀。这种思路的优雅之处在于它把“对多个字符串求公共前缀”的问题转换成了“在Trie树上找最早出现分支的节点”的问题。面试的时候如果你能主动提到这种关联即使你不写完整Trie实现面试官也会认为你对数据结构的理解是成体系的而不是一个一个孤立的知识点。有向无环图和并发前缀匹配也有类似思想比如HTTP路由的分段匹配、数据库索引的复合前缀匹配都属于“前缀”这一概念的变体。学会了这个基础你去看很多框架的源码会突然觉得容易理解很多。5.3 一套“从看懂到会写”的刷题心法最后分享一个我自己的刷题套路对最长公共前缀这种“中等偏简单”的题特别好用。第一步把题目的所有边界条件自己列出来然后带着这些边界条件去读示例。第二步用人话描述你的暴力解法把它说给一个虚拟的同事听看他说不说得通。第三步先写正确但耗时的解法跑通所有测试用例再思考怎么优化。第四步优化之后不急着提交写几个“畸形输入”测试一下空数组、单个元素、全同字符串、完全无公共前缀、超长字符串和短字符串的混搭。这个流程看着慢但练下来之后你会发现笔试和面试的能力提升效率远超直接刷题。刷题不是比谁刷得多而是比谁能从一道题里抽取到一套可复用的思维工具。最长公共前缀这个工具里面塞进了边界处理、复杂度计算、多方案选型、从暴力到优化的跃迁路径四个全占了。我个人带实习生的经验是把一个核心概念嚼透胜过囫囵吞枣地刷三五十道题。毕竟面试官不傻真正有没有理解三言两语就能试出来。