LeetCode热题100里，最长公共前缀（原题第14题）绝对是我见过最“反差萌”的一道题。名字听着像个easy题，看一眼题干：给定一个字符串数组，找出这些字符串的最长公共前缀，没有就返回空字符串。很多人的第一反应是：这不就是个两重循环的事吗？但当我把四种解法都刷了一遍之后，才发现这道题把字符串处理、边界控制、分治思想、二分思想全串起来了，做一道题的收获抵得上瞎刷十道。
这道题适合所有在刷LeetCode的人，尤其是刚开始撸热题100的同学。它看起来简单，实际上对循环边界的敏感度要求很高，很多新手会在“字符串越界”这个点上栽跟头。这篇就按我实际刷题的过程，从题干定义、四种解法、复杂度对比到边界测试，完整梳理一遍，希望看完你能把这道题吃得透透的。
1. 题目到底在问什么：先吃透最长公共前缀的定义
1.1 题干和基本判定逻辑
LeetCode第14题的完整描述是：编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串""。
官方给了两个示例：
strs = ["flower", "flow", "flight"]，输出"fl"，因为这三个字符串从头开始重合的部分就是fl。strs = ["dog", "racecar", "car"]，输出""，因为第一个字符就互不相同，公共前缀为空。
这里有一个最容易被忽略、却最关键的点：公共前缀一定是从每个字符串的第0位开始连续匹配的。它不是子序列，不是子串里最长的那段，而是所有字符串从开头逐字符对齐后，共同拥有的那一小段。换句话说，只要某个字符串的第k位和对齐位置不同，那么长度为k+1及以后的所有可能性全部作废。
很多人会把这道题和“最长公共子串”搞混。前者要求从头对齐，后者不要求位置一致；前者用扫描思路几行就写完，后者得上动态规划。题目名里的“前缀”两个字就是最大的提示。
还有一个隐含的细节：返回的公共前缀，本身必须是某个字符串的前缀。当所有字符串完全相同，或者只有一个字符串时，最长公共前缀就是整个字符串本身。所以strs = ["a"]的答案是"a"，不是""。
1.2 这道题在考察哪些基本功
说实话，这道题作为easy题，单看知识点并不高深，但它把几个基本功全串在了一起：
- 字符串按索引访问：不同语言对字符串取值的方式不同，但都要求你清楚知道访问到越界时的行为。
- 双重循环的控制：外层决定比较哪一位，内层决定比较哪个字符串，两个循环的终止条件需要同时考虑。
- 边界条件的敏感度：空数组、数组只有一个元素、数组里有空字符串、某个字符串特别短，这些情况全都要兜住。
- 多种算法思路的切换：横向扫描、纵向扫描、分治、二分，四种解法看着思路完全不同，但本质都在处理同一个问题。
LeetCode热题100之所以把这道题排进去，就是想用它来考察一个程序员在面对“看似简单但边界极多”的问题时，能不能保持头脑清醒。我在公司面试别人时也经常出这题，目的不是看对方能不能AC，而是看他能不能把边界说清楚、把复杂度算明白。
2. 解法一：横向扫描，最符合直觉的写法
2.1 核心思路与代码
横向扫描是我最先想到的写法：先拿第一个字符串当基准，然后用它和第二个字符串比较，得到第一个公共前缀；再用这个前缀和第三个字符串比较，得到新的前缀……以此类推。每比较一次，前缀只会变短或不变，不会变长。
from typing import List def longestCommonPrefix(strs: List[str]) -> str: if not strs: return "" prefix = strs[0] for i in range(1, len(strs)): s = strs[i] j = 0 # 注意两个长度都要判断，防止越界 while j < len(prefix) and j < len(s) and prefix[j] == s[j]: j += 1 prefix = prefix[:j] if not prefix: return "" return prefix代码逻辑很直白：初始时prefix就是第一个字符串；j用来记录当前前缀和下一个字符串重合的长度；循环结束后用切片截断更新prefix。一旦前缀被截成空字符串，说明连第一个字符都不一样，直接返回""即可。
这里有一个工程上的细节：为什么不用prefix = prefix[:j]以外的写法？因为切片在Python里会创建新字符串，但长度很小、次数可控，性能影响可以忽略。如果你特别在意内存分配，也可以改成记录一个max_len，最后再统一切片，后面我细说。
2.2 时间复杂度分析为什么这么写最稳妥
设字符串数组长度为n，所有字符串的字符总数为S。最坏情况下，每个字符串都比较到了和前缀不同的位置才停下，所以内层循环的总执行次数不超过S，时间复杂度是O(S)。最好情况是第一个字符串和第二个字符串在第0位就不一样，一轮就结束，复杂度直接降到O(1)。
空间复杂度上，除了存输入和输出，只用了常数个额外变量，所以是O(1)。虽然Python的切片会产生临时字符串，但瞬时占用也属于常数级别（取决于公共前缀长度），在LeetCode的判定环境下不作为额外空间计算。
横向扫描最大的优点是：思路足够线性，几乎不需要绕弯。面试时遇到这题，先说这个解法可以大概率拿到基准分。它不会是最优解，但一定不是错解，而且代码出bug的概率最低。
3. 解法二：纵向扫描，省内存还能提前返回
3.1 按列比较的思路
横向扫描的痛点是每次都要拿出整个前缀去和下一个字符串碰撞，哪怕第一个字符就已经不一致，也得把前面的循环跑完。纵向扫描则是换了个维度：按列比较。什么意思？先看所有字符串的第0个字符是否相同，再看第1个字符，以此类推。一旦发现某一列不匹配，或者某个字符串已经到头了，立即返回前面匹配到的部分。
from typing import List def longestCommonPrefix(strs: List[str]) -> str: if not strs: return "" for j in range(len(strs[0])): ch = strs[0][j] for i in range(1, len(strs)): # j >= len(strs[i]) 表示第i个字符串已经到头了 if j >= len(strs[i]) or strs[i][j] != ch: return strs[0][:j] return strs[0]外层循环以第一个字符串的长度为上限，内层循环从第二个字符串开始逐个比较第j位。j >= len(strs[i])这个条件一定要放在or的前面，因为Python的or短路求值：一旦判断为真，后面strs[i][j]就不会执行，从而避免索引越界报错。这个细节是纵向扫描最容易踩的坑。
3.2 与横向扫描的对比和适用场景
从时间复杂度的数量级来看，纵向扫描也是O(S)，但它的平均表现通常比横向扫描好，原因很简单：它是一列一列推进的，经常能在很短的公共前缀处提前返回。比如["ab", "ac", "ad"]，横向扫描要比对完a再比对到b和c不同才停；纵向扫描则直接逐列扫，第一列三个字符串都是a继续，第二列发现b、c、d不一致，立即返回"a"。虽然两者在这个例子里差别不大，但在数据量大的场景下，纵向扫描省去了反复截断字符串的开销。
内存方面，纵向扫描全程没有切片生成新字符串，只是在发现不匹配时切一次返回结果，所以空间占用更干净。
适用场景上，如果字符串总体很长、但公共前缀很短，纵向扫描优势明显。如果公共前缀接近整个字符串的长度，两者差别不大。我在实际做题时会优先写纵向扫描，因为它代码更短，而且天然规避了横向扫描反复更新前缀带来的思维负担。
4. 解法三：分治与二分，面试加分项
4.1 分治法：把数组拆成左右两半再合并
前三章如果说是常规操作，分治和二分就是这道题的进阶玩法。分治的思路不复杂：把字符串数组从中间一分为二，分别求出左半部分的最长公共前缀和右半部分的最长公共前缀，最后再对这两个前缀取一次公共部分。递归下去，直到子数组只剩一个字符串。
from typing import List def longestCommonPrefix(strs: List[str]) -> str: if not strs: return "" def lcp(left: int, right: int) -> str: if left == right: return strs[left] mid = (left + right) // 2 l = lcp(left, mid) r = lcp(mid + 1, right) i = 0 while i < len(l) and i < len(r) and l[i] == r[i]: i += 1 return l[:i] return lcp(0, len(strs) - 1)递归出口是left == right，直接返回对应字符串；合并阶段把两个子结果逐个字符比较，找出公共部分。这个写法的时间复杂度仍然是O(S)，但递归栈会带来额外的空间开销，最坏情况下递归深度为O(log n)，每层合并需要O(m)的空间，其中m是公共前缀长度，所以总空间是O(m log n)。
分治法在面试里的价值不在性能，而在展示你具备“把大问题拆成小问题”的思维方式。实际工作中，如果字符串数组分布在多台机器上，横向或纵向扫描都需要汇总后处理，而分治天然适合分布式场景：每个节点算自己的部分，最后再归并。这也是很多大厂面试官追问这题时想听到的扩展点。
4.2 二分查找：对公共前缀长度出手
二分查找的思路更有意思。公共前缀的长度一定在0到min_len之间，其中min_len是所有字符串中最短的那个的长度。我们对这个长度做二分：猜一个中间值mid，如果所有字符串的前mid个字符完全一样，说明公共前缀可能更长，把长度下限提高；否则说明当前猜长了，把长度上限降低。最后收敛到的长度就是答案。
from typing import List def longestCommonPrefix(strs: List[str]) -> str: if not strs: return "" min_len = min(len(s) for s in strs) low, high = 0, min_len def is_common(mid: int) -> bool: prefix = strs[0][:mid] return all(s.startswith(prefix) for s in strs[1:]) while low < high: mid = (low + high + 1) // 2 if is_common(mid): low = mid else: high = mid - 1 return strs[0][:low]这段代码有两个细节需要注意。第一，min_len取的是所有字符串长度的最小值，因为公共前缀不可能超过任何字符串的长度。第二，二分时用mid = (low + high + 1) // 2而不是(low + high) // 2，原因是当low和high相邻时，后者会让mid等于low，如果is_common(mid)成立，low不会更新，陷入死循环。+1向上取整就能避免这个问题，这是我踩过坑之后养成的习惯，建议直接记住。
复杂度上，二分本身需要O(log m)轮，其中m是最短字符串的长度；每一轮is_common要做n次startswith判断，每次判断比较mid个字符。所以总时间复杂度是O(n * m * log m)。虽然理论上比O(S)要大，但因为二分的常数小、提前返回频繁，实际跑起来往往也不慢。空间复杂度O(1)。
5. 四种解法横向对比与实战测试用例
5.1 复杂度对照表
为了看起来直观，我把四种解法的复杂度整理成了一张表。这里的S表示所有字符串的字符总数，n表示字符串个数，m表示所有字符串中最短字符串的长度。
| 解法 | 时间复杂度 | 额外空间复杂度 | 特点 |
|---|---|---|---|
| 横向扫描 | O(S) | O(1) | 思路直观，代码简单，适合秒AC |
| 纵向扫描 | O(S) | O(1) | 按列推进，提前返回快，内存分配少 |
| 分治法 | O(S) | O(m log n) | 递归拆解，面试可拓展到分布式 |
| 二分查找 | O(n * m * log m) | O(1) | 思路新颖，强调对长度做二分 |
实际面试中，横向扫描和纵向扫描二选一作为基础答案就够了。分治和二分属于加分项，尤其是二分这个思路，很多人想不到还能对“长度”这个维度做文章，你主动提出来会很加分。
5.2 边界条件与测试用例设计
做算法题最忌讳只看示例数据。示例数据只是让你理解题目，真正决定代码正确性的是隐藏的边界条件。这道题我整理了一份自测用例清单，建议直接抄去跑：
test_cases = [ (["flower", "flow", "flight"], "fl"), (["dog", "racecar", "car"], ""), (["a"], "a"), ([""], ""), ([], ""), (["ab", "a"], "a"), (["", "b"], ""), (["aaa", "aa", "aaa"], "aa"), (["same", "same", "same"], "same"), (["abc", "abcd", "abcde"], "abc"), ]逐个说下为什么要测这些：
["flower", "flow", "flight"]是标准示例，测正常情况。["dog", "racecar", "car"]测完全无公共前缀的情况。["a"]测数组只有一个元素，此时公共前缀是整个字符串。[""]测数组里有空字符串，空字符串和任何字符串取公共前缀都是空。[]测空数组，直接返回空字符串，这要求代码第一行就做判空处理。["ab", "a"]测第二个字符串比第一个短，纵向扫描的越界判断在这里起作用。["", "b"]测第一个字符串为空字符串的情况。["aaa", "aa", "aaa"]测所有字符串相同的前缀不是第一个字符串本身，而是更短的值。["same", "same", "same"]测所有字符串完全相同，公共前缀等于整个字符串。["abc", "abcd", "abcde"]测公共前缀恰好是某个较短字符串的全长。
每一条用例都对应一类找bug的方向。我见过很多人AC了代码但漏掉["ab", "a"]这个用例，导致面试官随口一问就露馅。所以强烈建议刷题时把边界用例写在代码注释里，或者单独记在本地，形成自己的用例集。
6. 从这道题延伸出去：面试官真正想看你什么
6.1 变形题与后续学习建议
最长公共前缀做熟之后，有几个变形和延伸可以顺手刷掉，对巩固很有帮助：
- 字符串数组找最长公共后缀：把每个字符串反转，再用最长公共前缀的解法，最后把结果反转回来。能理解这个转化，说明你掌握了复用的思路。
- 多个字符串的字典序最小前缀：结合排序，先排字典序，再比较第一个和最后一个字符串的公共前缀，这其实是另一种利用排序性质解题的思路。
- 前缀匹配的进阶：字典树Trie：LeetCode的
实现Trie前缀树就是这道题的最终进化版。把字符串逐个插入字典树，从根节点开始往下走，直到遇到分叉节点，走过的路径就是最长公共前缀。字典树适合处理大量字符串的前缀查询，在自动补全、拼写检查场景里很常见。
如果时间有限，我的建议是先吃透横向和纵向扫描，然后把分治和二分各写一遍，最后再看一眼字典树解法。这样由浅入深，既掌握了热题100的必考答案，也顺手预习了更进阶的数据结构。
6.2 我的实操心得和踩坑记录
最后说点个人经验。我在LeetCode上第一次提交这道题时，用的就是最普通的横向扫描，但犯了个低级错误：没有判断空数组。结果strs[0]直接IndexError，红了一大片。后来每次写字符串类题目，我第一行必写边界判断，已经成本能了。
纵向扫描的越界判断也是重灾区。j >= len(strs[i])或strs[i][j]的顺序写反，或者漏掉长度判断，都会在测试用例["ab", "a"]上报错。调试这类问题的时候，别急着看完整的错误堆栈，先用最简单的两个字符串的用例排查，定位效率高很多。
还有一个经验是关于刷题节奏的。热题100里的easy题，AC不是终点，把题解区的高票答案全部过一遍才是真正的收获。最长公共前缀这题尤其如此，只看一种解法你会觉得题目很平淡，但当你把横向、纵向、分治、二分四种解法都写一遍，你对“同一个问题可以有多种切入角度”这件事的体感会完全不一样。以后再碰到hard题，就不会只困在第一个想法里出不来。
我在实际面试别人时，最长公共前缀这道题也常被用作热身题。我观察到的现象是：能写出横向扫描的候选人占大多数；能把纵向扫描的越界讲清楚的少一些；主动提到分治或二分的凤毛麟角。所以如果你已经看到这里，其实你已经比绝大多数刷题者多想了一层。这道题的价值不在于你背下几种解法，而在于你通过它建立起来的边界意识和多角度思考习惯，这些才是刷LeetCode真正能沉淀下来的东西。
