如果你准备过算法面试，十有八九会遇到这么一道题：给你一个字符串数组，让你返回这些字符串的“最长公共前缀”。看着简单，好像两分钟就能写出来，但真正动手之后你会发现，边界情况、代码风格、复杂度分析、甚至面试官追问的变体，都能把这道题从“签到题”变成“分水岭”。
作为一个经常帮别人做代码评审、也经常被问到字符串类题目的人，我一直觉得“最长公共前缀”是特别适合用来训练解题思路的题目：它解法多，每种解法的思路差异很大，而且可以从一道题延伸到二分、分治、字典树等一大堆知识点。这篇文章我就把自己在实际刷题、面试、以及工程应用中对这道题的全部心得整理出来，从最朴素的方案讲到面试官喜欢的优化方案，再到边界情况的坑，一次性说透。
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 = "fl"，s = "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 用纵向扫描的方式处理，只花了几十毫秒，代码十几行。如果当时我没学过这道题，大概会写个双重循环，效率差很多。技术面试里的很多题目，看起来和日常工作关系不大，但真正到需要的时候，你会庆幸当初多花了半小时研究它的多种解法。
“最长公共前缀”这道题还有一个特点：它几乎覆盖了所有基础算法设计思想，却又不复杂到让人劝退。我建议你在刷题时，不要只满足于提交通过，而是把文中的几种解法都亲手写一遍。等你写出五种解法并分析清楚各自适用场景后，再看其它字符串题目，会轻松很多。
