如果你准备过算法面试十有八九会遇到这么一道题给你一个字符串数组让你返回这些字符串的“最长公共前缀”。看着简单好像两分钟就能写出来但真正动手之后你会发现边界情况、代码风格、复杂度分析、甚至面试官追问的变体都能把这道题从“签到题”变成“分水岭”。作为一个经常帮别人做代码评审、也经常被问到字符串类题目的人我一直觉得“最长公共前缀”是特别适合用来训练解题思路的题目它解法多每种解法的思路差异很大而且可以从一道题延伸到二分、分治、字典树等一大堆知识点。这篇文章我就把自己在实际刷题、面试、以及工程应用中对这道题的全部心得整理出来从最朴素的方案讲到面试官喜欢的优化方案再到边界情况的坑一次性说透。1. 题目拆解与解题思路的底层逻辑1.1 题目到底在问什么先花一分钟把题目本身说清楚。给定一个字符串数组比如[flower, flow, flight]需要返回这些字符串共同的前缀也就是从第一个字符开始所有字符串都相同的那一段。上面这个例子的答案是fl。如果没有公共前缀就返回空字符串。这里的关键词是“前缀”。前缀就是从字符串开头连续截取的子串不是任意位置的子串。所以一个字符串abcdef的前缀可以是a、ab、abc但不能是bcd。很多人在讨论公共子串的时候会不小心把前缀和子串搞混第一步就要明确这个定义。这个问题的本质其实是“多个集合的交集”只不过这里的集合不是普通元素而是一个字符串的“前缀集合”。我们把每个字符串的所有前缀看成一个集合那么最长公共前缀就是这些集合交集中最长的那个元素。理解到这个层面后面所有解法都能串起来了横向扫描是逐串求交集纵向扫描是按位判断是否存在某个字符在所有字符串中出现二分和分治则是用不同的方式组织这个求交集的过程。题目虽然简单但它非常适合作为面试热身题。原因是它包含了几种典型的算法设计思维暴力遍历、空间换时间、分而治之、二分答案以及利用排序后的性质。可以说把这道题吃透你对字符串题目的整体感觉会好很多。1.2 复杂度视角下的解法地图在开始写代码之前先建立一个全局的复杂度概念。假设数组里有 n 个字符串所有字符串的总长度是 S最短字符串的长度是 m。不同解法的时间复杂度会落在不同的区间解法时间复杂度最坏空间复杂度核心思想横向扫描O(S)O(1)两两求公共前缀逐步缩小纵向扫描O(S)O(1)按列扫描所有字符串分治法O(S log n)O(log n)分解为子问题再合并二分答案O(n·m·log m)O(1)对公共前缀长度二分排序后比较首尾O(n·log n·m)O(1)利用字典序的区间性质注意横向扫描和纵向扫描的时间复杂度在最坏情况下其实都是 O(S)但实际运行效率不同。横向扫描每次都是用当前公共前缀和一个新字符串重新比较如果公共前缀很长每轮都会重新比较很多字符纵向扫描则是所有字符串同时推进一旦发现不匹配就立刻终止通常更早退出。为什么我会把“解法地图”先摆出来因为面试和做题有一个本质区别做题追求通过面试追求“展示思维过程”。如果你一开始就说“我知道五种解法”面试官会认为你准备过如果你能根据输入规模现场推导出适合的方案面试官才会觉得你真的理解。后面每一节我会详细讲这些解法分别适合什么场景。2. 主流解法逐一拆解与代码实现2.1 解法一横向扫描先说大部分人第一反应就能想到的方案先拿第一个字符串当作初始公共前缀然后依次和后面的每个字符串求“两个字符串的最长公共前缀”不断缩小结果。用 Python 写出来大概是这样的def longest_common_prefix(strs): if not strs: return prefix strs[0] for s in strs[1:]: # 不断缩短prefix直到它是s的前缀 while not s.startswith(prefix): prefix prefix[:-1] if not prefix: return return prefix代码非常短但有一个细节值得解释为什么用startswith而不是手动逐字符比较因为语言内置方法通常做了底层优化而且语义清晰。但在面试手写时更推荐展示逐字符比较的版本因为面试官更想看到你理解比较过程而不是只会调 API。另一个版本是每次用循环找出两个字符串的公共前缀def lcp_of_two(a, b): i 0 while i len(a) and i len(b) and a[i] b[i]: i 1 return a[:i]然后横向扫描就变成了不断调用lcp_of_two。这样做的好处是逻辑更透明也方便后面和其他思路组合。复杂度方面最坏情况是数组里所有字符串都一样长且内容一样比如一百个长度为一万的相同字符串。此时每次比较都要完整跑一遍总比较次数接近总字符数 S所以时间复杂度 O(S)。空间复杂度只有结果字符串的占用可以认为 O(1)。这个方案的优点是直观、几乎不会错缺点是如果第一个字符串特别长而后面某个字符串很短且差异很大会白做很多比较。不过对于普通输入规模它已经完全够用。2.2 解法二纵向扫描横向扫描是“一个字符串一个字符串地推进”纵向扫描则是“一个字符一个字符地推进”。思路是从第 0 位开始检查所有字符串的第 0 个字符是否相同如果相同继续看第 1 位直到某一位出现不同或者某个字符串已经结束。def longest_common_prefix(strs): 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]这个版本我用 Python 写的但思想同样适用于 Java、C、Go 等语言。关键点在于内层循环的顺序先判断i len(s)再访问s[i]这个顺序不能反。一旦某个字符串长度不够说明公共前缀最长就到当前位置直接返回即可。纵向扫描的优点有两个一是当最短字符串很短时循环次数很少二是它天然适合“提前终止”。比如数组[ab, abc, abd]扫描到第 2 位发现b和d不同立刻返回ab比较次数非常少。实际执行过程可以这样直观感受strs [flower, flow, flight] 第0位f f f继续 第1位l l l继续 第2位o 与 o 与 i 不同返回 fl这个方案是面试中我最推荐的首选答案。它在时间复杂度上和横向扫描同为 O(S)但常数更小理解起来也不难。更重要的是它后续可以很自然地引出“字典树”和“多字符串匹配”的话题。2.3 解法三分治法如果面试官要求你“换一种思路”或者问题变成“需要并行计算”分治法就很合适。核心思想把数组从中间切开分别求出左半部分的最长公共前缀和右半部分的最长公共前缀然后再把这两个结果合并成一个公共前缀。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_lcp divide_conquer(strs, left, mid) right_lcp divide_conquer(strs, mid 1, right) return common_prefix_of_two(left_lcp, right_lcp) def common_prefix_of_two(a, b): i 0 while i len(a) and i len(b) and a[i] b[i]: i 1 return a[:i]分治法的时间复杂度要稍微注意一下。很多人只记住“分治是 O(S log n)”但这个结论需要解释。因为合并两个子结果时最坏情况下需要比较两个子公共前缀的全部长度。如果所有字符串完全相同每一层合并时每个字符都会被比较一次总共 log n 层所以最坏是 O(S log n)。空间复杂度主要来自递归调用栈是 O(log n)。分治法的价值不体现在“运行更快”而体现在“结构更漂亮”。它把一个整体问题拆成了互不依赖的子问题天然适合多线程或多机并行。如果你在面试中提到“如果字符串数量巨大可以考虑分治加并行”这会是加分项。2.4 解法四二分答案这道题还有一个很多人想不到的解法对“公共前缀的长度”做二分查找。为什么可以二分因为公共前缀的长度具有单调性如果长度为 k 的公共前缀存在那么长度小于 k 的公共前缀一定也存在如果长度为 k 的公共前缀不存在那么长度大于 k 的公共前缀更不可能存在。所以我们可以在0到最短字符串长度之间二分查找最大的可行长度。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 if is_common_prefix(strs, mid): low mid else: high mid - 1 return strs[0][:low] def is_common_prefix(strs, length): prefix strs[0][:length] for s in strs[1:]: if not s.startswith(prefix): return False return True注意二分细节使用low high 1向上取整避免死循环。每次判定需要遍历所有字符串的前mid个字符所以单次判定的时间复杂度是 O(n·mid)。最坏情况总复杂度是 O(n·m·log m)其中 m 是最短字符串长度。坦白说二分答案在这个题目上并不是性能最优的因为横向和纵向扫描都能做到 O(S)。那为什么还要掌握它因为它是一种通用的解题范式尤其适合“求最值但不好直接求”的问题先把求最值转换成判定性问题再用二分法在可行域里搜索。这种思想在“分割数组的最大值”“爱吃香蕉的珂珂”等题目里非常常见。掌握这道题的二分写法等于提前训练了那类题。2.5 解法五排序后比较首尾最后一个解法很适合作为“奇招”来展示先把字符串数组按字典序排序然后只需要比较排序后第一个字符串和最后一个字符串的公共前缀。def longest_common_prefix(strs): if not strs: return strs.sort() a strs[0] b strs[-1] i 0 while i len(a) and i len(b) and a[i] b[i]: i 1 return a[:i]为什么排序后只需要看首尾因为字典序排序会把具有相同前缀的字符串排在相邻区域。对于任意一个中间位置的字符串它的字典序一定介于第一个和最后一个之间因此如果首尾两个字符串前 k 个字符相同那么中间字符串的前 k 个字符也必须相同否则它就无法落在字典序的区间里。这是一个很漂亮的数学性质证明过程也不复杂值得在面试时讲出来。这个解法的代码量可以说是所有方案里最少的但代价是引入了排序的 O(n log n) 复杂度而且排序本身会修改原数组。如果题目允许修改输入它是不错的备选如果要求不能修改原数组就需要先复制一份空间开销就变成 O(S)。我个人的建议是这个解法可以作为面试中的“额外补充”用来展示你的知识广度但不要把它当作主回答。因为面试官听到“先排序”后通常会追问“为什么可以排序”你要能立刻讲清楚背后的字典序区间原理。2.6 五种解法对比与实战选型把五种解法放在一起看你会发现它们其实代表了不同的算法设计哲学维度横向扫描纵向扫描分治法二分答案排序首尾思路基础迭代缩小结果按位推进分而治之二分搜索排序后性质最坏时间复杂度O(S)O(S)O(S log n)O(n·m·log m)O(n·log n·m)空间复杂度O(1)O(1)O(log n)O(1)视是否复制而定代码难度低低中中极低面试推荐顺序第二选择首选体现深度体现广度巧妙但需证明如果在面试手写我首推纵向扫描因为它逻辑最清晰、边界最简单而且天然能说明你是“按字符思考”的。写完纵向扫描之后可以主动补一句“如果字符串数量巨大我会考虑分治法让多个线程分别计算子数组的公共前缀再合并。”这句话能立刻让你的回答从“会做题”升级到“有工程思维”。3. 边界条件、测试用例与易错点全梳理3.1 所有边界情形一个都不能漏“最长公共前缀”这道题本身不难但因为边界情况多实际写起来非常容易翻车。我把常见边界情况全部列出来空数组[]此时没有任何字符串按题目约定应返回空字符串。一定不能直接访问strs[0]否则数组越界。数组中只有一个字符串[abc]公共前缀就是它本身。任何解法都应该能正确处理但有些人在写二分或递归时容易漏掉。数组中有空字符串[, abc]公共前缀必然是空字符串。因为空字符串没有任何前缀和任何字符串的公共前缀都是空的。如果横向扫描时第一个字符串是空串prefix直接为空后续循环会立刻返回。所有字符串完全相同[abc, abc, abc]应返回完整的abc。这种情况最容易在“提前终止”写错时出问题比如纵向扫描里循环条件写成了i len(strs[0]) - 1就会少截一位。只有一个字符相同[a, ab]应返回a。注意结束条件是相等字符后面一个位置不相等或越界。大小写敏感a和A是不同的公共前缀为空。不需要做任何大小写归一化。Unicode 字符中文字符、emoji 在 Python 中按字符索引没有问题但如果你用字节数组处理要小心 UTF-8 编码下中文字符占多个字节逐字节比较会得出错误前缀。空字符串出现在数组中间比如[ab, , ac]正确返回。横向扫描在遇到第二个字符串时就会返回纵向扫描会在i len(s)时返回。很多人写这道题时不是算法不会而是边界条件没想全。我的建议是拿到一道字符串题目先花三十秒把输入的所有可能情况想一遍尤其是空串、单元素、全相同。这些情况往往能直接决定你的代码是“一次通过”还是“debug 半天”。3.2 手写代码时最容易踩的五个坑以下五个错误是我在实际评判别人代码时反复看到的每一个都值得单独提醒坑一横向扫描时忘记更新循环边界。有人会把prefix更新放在循环体末尾但中间一旦发现prefix为空没有及时 return导致下一轮继续用空串去比较。最好在每次缩短前缀后立刻判断是否为空。坑二纵向扫描时把越界判断放在字符比较之后。比如写成if s[i] ! ch or i len(s)。当s比strs[0]短时s[i]在越界判断之前就会被访问直接抛异常。顺序很重要先判断i len(s)再访问s[i]。坑三二分答案时用了low high而不是low high 1的中点。当区间缩小到两个相邻元素时low high // 2会一直取到低位导致死循环。二分求最大值通常要向上取整。坑四把startswith和“前缀相等”混为一谈。s.startswith(prefix)判断的是s是否以prefix开头。但如果prefix拥有一部分相同的字符但不完整比如prefix fls flower这没问题但有些人会误以为它可以用来比较“两个字符串是否互为前缀”这是不对的。坑五排序解法中直接修改了原数组。如果面试官说“不能修改输入”但你直接对strs.sort()那就等于改变了原数组很可能被扣分。稳妥的写法是sorted_strs sorted(strs)。这些坑看起来很小但面试手写代码时一个越界异常或死循环会比“思路不清晰”更致命。因为面试官会怀疑你的代码手感不够扎实。3.3 一套可以直接抄的测试用例写完成代码后建议用下面的测试用例快速自测输入期望输出备注[]空数组[]只有一个空串[a]a单元素[abc, abc, abc]abc全部相同[flower, flow, flight]fl标准示例[dog, racecar, car]完全无公共前缀[ab, a, abc]a最短串决定答案[aaa, aa, a]a逐级缩短[c, c]c两个相同单字符我实测下来只要把这些用例全部跑通你的代码基本不会有问题。特别是第二、三、四行很多人会漏掉这三个用例能帮你迅速发现大部分 bug。4. 面试实战从“会做”到“高分”4.1 拿到题目后应该怎么思考如果在面试现场遇到这道题我建议你按下面的顺序推进而不是直接闷头写代码。先澄清需求。尽管题目本身已经说得很清楚但你依然可以快速确认几个问题“数组为空时返回空字符串是吧”“字符串是否是大小写敏感的”“是否要考虑 Unicode 字符”这样做有两个好处一是展示你考虑问题全面二是避免后续因为理解偏差而返工。然后说暴力思路。不要一上来就讲二分和分治先讲最朴素的想法“我可以先拿第一个字符串作为候选答案然后依次和后面的字符串比较更新。”原因很简单面试官需要看到你的思维过程是递进的而不是上来就背方案。接着做复杂度分析。明确说出 O(S) 和 O(1) 空间然后提出优化“不过如果最短字符串很短纵向扫描可以更快返回因为它按列推进。”这个过渡自然且加分。如果你只说结论不说理由面试官大概率会追问。最后有余力时补充一句“如果输入规模特别大我考虑分治加并行或者构建字典树一次性处理。”即使不深入写代码这句话也会让面试官觉得你知识面广。4.2 高频追问与应对策略面试官可能会在写完基础解法后抛出一系列变体问题提前准备才不会慌。追问一如果字符串数量非常多内存放不下怎么办核心思路是把问题分片处理。分治法天然适合这种场景可以把字符串分成多组分别求出每组的公共前缀再对所有组的前缀求公共前缀。甚至可以在多台机器上并行。关键是向面试官说明公共前缀的长度只会随着合并而缩短或保持不变不会变长。追问二如果单个字符串特别长怎么办纵向扫描是最合适的因为它一旦遇到不匹配就立刻停止不会像横向扫描那样反复扫描完整长字符串。更进一步的思路是先用最短字符串的长度做上限把扫描范围压缩到最短长度内。也可以提一下字典树把每个字符串插入前缀树中公共前缀就是从根节点到第一个分支节点之间的路径。追问三能不能不用任何额外空间除了分治法需要递归栈空间、排序法如果复制数组需要额外空间之外横向扫描、纵向扫描、二分答案都能做到 O(1) 额外空间。如果你选择排序法就一定要说明你是原地排序、不复制否则会在这里被扣分。追问四如果要求能用流式输入每次只给一个字符串怎么处理这其实是一个在线算法问题。维护一个变量prefix每次读入一个新字符串就用当前prefix和它求公共前缀不断更新。这本质上就是横向扫描的在线版本复杂度依然可控。追问五如果允许修改输入你会选哪种解法我会选排序法代码极其简洁。但我要强调排序法的时间复杂度是 O(n log n·m)在 n 很大时不如纵向扫描。所以即使允许修改纵向扫描依然是综合最优。4.3 一个真实场景中的变体问题我之前在评审一段配置管理工具代码时遇到过一道和这道题几乎一模一样的变体问题。场景是这样的系统有大量文件路径需要统一迁移到新目录为了生成新的配置模板需要找出这些路径的公共目录前缀。比如有下面这些路径/var/www/html/client/css/theme.css /var/www/html/client/js/app.js /var/www/html/client/img/logo.png需要提取出的公共前缀是/var/www/html/client/但要注意不能把client后面的/截断否则生成的目录会不合法。这跟“最长公共前缀”非常相似但有个工程上的差异字符串的边界是路径分隔符/而不是字符本身。也就是说不能简单地在字符级别比较需要在路径层级划分后按目录分段取公共前缀。当时我的做法是先用/分割所有路径得到目录数组然后对这些数组逐段比较找到公共目录段的数量再重新拼接。本质上就是纵向扫描的变体只不过比较单位从“字符”变成了“目录段”。这个小例子说明刷题的价值不只是应付面试。它会变成一种思维工具在你处理真实问题时潜移默化地提供思路。5. 算法的生活化理解与工程延伸5.1 用生活里的例子把“公共前缀”讲明白公共前缀这个概念并不抽象生活中到处都有。通讯录里的分组就是一个很好的例子。你有一堆联系人想按姓氏拼音首字母分组那么同一个分组里的人他们的名字拼音就共享一个首字母前缀。如果你想给一家人发消息那这家人可能存在共同的姓张一、张三、张四共享前缀就是“张”。再比如你在目录里组织文件report_2024_01.txt、report_2024_02.txt、report_2024_03.txt它们的公共前缀是report_2024_。想批量归档时知道这个前缀就能快速筛选出这些文件。网络路由里的“最长前缀匹配”也是同一个概念的进阶版本。路由表里存着很多 IP 前缀数据包到达时路由器会选择匹配位数最多的那个前缀来决定下一跳。虽然核心算法比我们讨论的复杂不少但它本质上也还是在解决“多个前缀之间如何匹配和比较”的问题。生活化理解的好处是你能在面试时用通俗例子把思路讲给面试官听这会显著提升沟通效率。尤其当面试官不是纯算法背景时一个“通讯录按姓分组”的例子比满口复杂度术语更容易让人接受。5.2 从“最长公共前缀”延伸到字典树这道题是所有字典树Trie类题目的敲门砖。如果你把多个字符串依次插入一棵前缀树中那么它们的公共前缀就是根节点下方直到第一个出现“分支或结束”的节点之间的路径。用字典树求公共前缀的时间复杂度是 O(S)空间复杂度也是 O(S)它更适合在字符串集合很大、后续还有大量前缀查询需求的场景中使用。举个例子在实现输入框的自动补全功能时如果只求一组单词的公共前缀用纵向扫描就够了但如果你需要频繁查询“以某个前缀开头的所有单词”字典树就比每次线性扫描快得多。很多人在刷题时会忽略这一点觉得“反正这道题用扫描就能过”但遇到海量数据场景数据结构的选择就很关键了。另外还有一个常见的延伸是“最长公共子串”它和“最长公共前缀”虽然只有两字之差但难度完全不同。最长公共子串不需要从开头对齐可能出现在字符串的任意位置通常要借助动态规划或后缀数组解决。面试中如果有人把这两个概念搞混我会直接判断他基础不牢。所以你在描述题目时务必把“前缀”两个字说清楚。5.3 我在实际工程中的使用心得说了这么多理论和代码最后分享一点实际工作中的体会。刚工作那几年我遇到字符串相关需求时脑子里只有“暴力循环”一个念头总想着怎么把所有可能性遍历一遍。后来刷题刷多了写命令行的批处理脚本、做配置文件合并、处理日志分析时都会不自觉地先想这个问题能不能转化成“公共前缀”或者“公共区间”问题有一次需要写一个脚本从几千条 URL 中提取出共同的基础路径以便在网关里配置统一的转发规则。几千条 URL 用纵向扫描的方式处理只花了几十毫秒代码十几行。如果当时我没学过这道题大概会写个双重循环效率差很多。技术面试里的很多题目看起来和日常工作关系不大但真正到需要的时候你会庆幸当初多花了半小时研究它的多种解法。“最长公共前缀”这道题还有一个特点它几乎覆盖了所有基础算法设计思想却又不复杂到让人劝退。我建议你在刷题时不要只满足于提交通过而是把文中的几种解法都亲手写一遍。等你写出五种解法并分析清楚各自适用场景后再看其它字符串题目会轻松很多。