1. 从一道"简单题"说起：最长公共前缀到底在考什么
LeetCode 第 14 题"最长公共前缀"，在题库里被标记为简单难度，很多人扫一眼题目描述——给一个字符串数组，找出所有字符串共有的最长前缀——脑子里立刻蹦出"两两比较"或者"拿第一个当模板逐个比对"的思路，然后几分钟就提交通过了。但我在带新人刷题的过程中发现，这道题真正值得聊的地方，恰恰藏在"简单"这两个字背后：它是一道典型的字符串边界处理题，也是一道能暴露你代码习惯好不好的"照妖镜"。
为什么这么说？因为这道题的输入有太多坑：数组可能为空、数组里可能只有一个字符串、字符串可能是空串、所有字符串可能完全没有公共前缀、公共前缀可能恰好等于最短的那个字符串本身。这些边界情况，面试官不会在题目描述里逐条列给你，但测试用例一个都不会少。我见过太多人本地跑样例通过，一提交就挂在[]、[""]、["a"]这种输入上。
这篇文章我会把这道题从思路选型、代码实现、复杂度分析到边界处理、常见翻车点，完整地拆一遍。适合刚接触 LeetCode 的初学者建立字符串题的处理直觉，也适合已经刷了几十道题、想把代码写得更"工程化"的中级选手对照检查自己的习惯。核心关键词就三个：最长公共前缀、字符串数组、边界条件。我会用 C++ 来写，但思路对任何语言都通用。
先说结论：这道题的最优解不是"两两比较"，而是纵向扫描或者分治，前者代码最短、最容易写对，后者在特定场景下更优雅。下面我一步步展开为什么。
2. 题目拆解与核心思路选型
2.1 题目到底在问什么
先把题目用大白话翻译一遍。给你一个字符串数组strs，比如["flower", "flow", "flight"]，你要找出一个字符串，它是数组里每一个字符串的前缀，并且是所有满足条件的前缀里最长的那个。上面这个例子的答案就是"fl"。
注意两个关键词：每一个和最长。"每一个"意味着只要有一个字符串不满足，这个前缀就不合法；"最长"意味着我们要在所有合法前缀里取长度最大的。这两个约束一叠加，其实就限定了答案的范围：答案的长度不可能超过数组里最短字符串的长度，因为前缀必须对最短的那个字符串也成立。
这个观察很关键，它直接给出了一个上界：答案长度 ≤ min(所有字符串长度)。很多优化思路都是从这个上界出发的。
2.2 四种主流解法对比
这道题至少有四种能拿得出手的解法，我把它们的核心逻辑、代码量和适用场景整理成一张表，方便你一眼看清差异：
| 解法 | 核心逻辑 | 时间复杂度 | 代码量 | 推荐度 |
|---|---|---|---|---|
| 横向扫描（两两比较） | 拿前两个求公共前缀，结果再和第三个比，依次类推 | O(S)，S 为所有字符总数 | 中等 | 一般 |
| 纵向扫描 | 按列比较，第 i 列所有字符串都相同才继续 | O(S) | 最短 | 强烈推荐 |
| 分治 | 数组一分为二，分别求前缀再合并 | O(S) | 较长 | 面试加分 |
| 二分查找 | 对前缀长度二分，每次验证 | O(S·log m) | 较长 | 了解即可 |
这里的 S 指的是所有字符串的字符总数，m 是最短字符串的长度。可以看到，横向扫描、纵向扫描、分治的复杂度都是 O(S)，差别主要在常数和代码可读性上。
2.3 为什么我首推纵向扫描
纵向扫描的思路特别符合人的直觉：把所有字符串想象成排成一列一列的字符矩阵，我们从第 0 列开始，一列一列往右看。如果某一列上所有字符串的字符都相同，说明这一列可以纳入公共前缀；一旦发现某个字符串在这一列没有字符（越界了）或者字符和别人不一样，立刻停止，前面所有列拼起来就是答案。
它的优势有三个。第一，代码极短，一个双重循环就能搞定，不容易写错。第二，天然处理边界，因为循环条件里就包含了"越界检查"，空数组、空串这些情况顺手就处理了。第三，提前终止，一旦发现不匹配马上返回，不需要把所有字符串都扫完，实际运行往往比理论复杂度更快。
横向扫描虽然也对，但它有个隐患：每次两两比较都会产生一个中间结果字符串，如果数组很长，这些中间字符串的创建和销毁是有开销的。而且横向扫描在遇到"第一个字符串特别长、后面都很短"的情况时，会做很多无用功。纵向扫描没有这个问题。
3. 纵向扫描的完整实现与逐行剖析
3.1 核心代码
先上代码，然后我逐行拆：
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; int n = strs.size(); int firstLen = strs[0].size(); for (int col = 0; col < firstLen; ++col) { char c = strs[0][col]; for (int i = 1; i < n; ++i) { // 两种情况需要停止：strs[i] 越界，或字符不匹配 if (col >= strs[i].size() || strs[i][col] != c) { return strs[0].substr(0, col); } } } return strs[0]; } };3.2 逐行拆解每个决策
第一行if (strs.empty()) return "";这是必须的防御性检查。题目约束里虽然说了数组长度至少为 1，但实际面试中面试官很可能故意给你一个空数组看你怎么反应。更重要的是，如果不检查，下面strs[0]就会越界访问，直接崩溃。养成"访问容器第一个元素前先判空"的习惯，能帮你躲掉一大类 bug。
int firstLen = strs[0].size();这里我选择以第一个字符串的长度作为外层循环的上界。为什么不用最短字符串的长度？因为找最短本身要遍历一遍数组，多一次 O(n) 的开销。而用第一个字符串的长度做上界是安全的：如果第一个字符串比答案长，内层循环会在越界检查时提前返回；如果它比答案短，那答案最多也就是它本身，循环自然结束。所以用第一个的长度既省事又正确。
外层循环for (int col = 0; col < firstLen; ++col)这里的col代表"列号"，也就是当前正在比较的字符位置。注意我用的是col而不是i，这是有意的命名习惯——在二维逻辑里，用row/col比用i/j可读性高得多，尤其是当内外层循环都叫i、j的时候，很容易搞混谁是谁。
char c = strs[0][col];把第一个字符串在当前列的字符取出来当"基准"。所有其他字符串都要和这个基准比。这里有个小优化点：把strs[0][col]存到局部变量c，避免在内层循环里反复访问strs[0]，虽然编译器大概率会帮你优化，但显式写出来更清晰。
内层循环for (int i = 1; i < n; ++i)从下标 1 开始，因为下标 0 是基准本身，不用和自己比。
关键判断if (col >= strs[i].size() || strs[i][col] != c)这是整段代码的灵魂。两个条件用||连接，顺序不能反。必须先判断越界，再判断字符是否相等。为什么？因为如果col >= strs[i].size()成立，说明第 i 个字符串已经比当前列短了，此时访问strs[i][col]就是越界访问，是未定义行为。C++ 的||有短路特性，左边为真时右边不会执行，所以把越界检查放左边是安全的。如果你手滑写反了，在某些编译器上可能侥幸不崩，但这是定时炸弹。
return strs[0].substr(0, col);一旦发现不匹配，立刻返回从 0 开始、长度为col的子串。注意substr(0, col)的第二个参数是长度不是结束下标，返回的是[0, col)这个区间，正好是前col个字符，也就是已经确认的公共前缀。
循环外的return strs[0];如果外层循环完整跑完都没触发返回，说明第一个字符串的每一个字符都是公共前缀的一部分，那答案就是第一个字符串本身。这个收尾很容易被漏掉，漏了就会编译报错"函数没有返回值"。
3.3 手动跑一遍样例
拿["flower", "flow", "flight"]走一遍：
- col=0：基准
f，flow[0]=f匹配，flight[0]=f匹配，继续。 - col=1：基准
l，flow[1]=l匹配，flight[1]=l匹配，继续。 - col=2：基准
o，flow[2]=o匹配，flight[2]=i不匹配，触发返回strs[0].substr(0, 2)="fl"。
结果正确。再拿["dog", "racecar", "car"]走一遍：col=0 时基准d，racecar[0]=r不匹配，直接返回substr(0,0)=""。也对。
4. 边界条件与常见翻车点实录
4.1 必须覆盖的边界用例
我把这道题容易翻车的输入整理成一张速查表，建议你写完代码后逐条自测：
| 输入 | 期望输出 | 考察点 |
|---|---|---|
[] | "" | 空数组防御 |
[""] | "" | 单元素空串 |
["a"] | "a" | 单元素非空 |
["", "b"] | "" | 含空串的数组 |
["abc", "abc", "abc"] | "abc" | 完全相同 |
["ab", "a"] | "a" | 答案等于最短串 |
["a", "ab"] | "a" | 第一个是最短的 |
["abc", "def"] | "" | 完全无公共前缀 |
其中["", "b"]和["a", "ab"]是最容易挂的两个。前者考察你对空串的处理，后者考察"第一个字符串最短"时循环能否正确结束。
4.2 三个高频翻车点
翻车点一：越界检查顺序写反。前面强调过，col >= strs[i].size()必须放在||左边。我见过有人写成strs[i][col] != c || col >= strs[i].size()，逻辑上等价但执行顺序错了，一旦越界就是未定义行为。这种 bug 在本地可能不崩，提交到线上环境换了编译器就炸，非常难查。
翻车点二：忘记处理空数组。直接strs[0]访问空 vector 是经典的段错误来源。哪怕题目保证非空，加一行判空也就一秒钟的事，收益远大于成本。
翻车点三：substr参数理解错。substr(pos, len)的第二个参数是长度，不是结束位置。有人想返回前 col 个字符，写成substr(0, col - 1)或者substr(0, col + 1)，结果差一位。记住：要前 col 个字符，就是substr(0, col)。
提示：写完代码后，别急着提交，先把上面表格里的用例在脑子里或者纸上跑一遍。这道题总共就几行代码，手动验证的成本极低，但能帮你挡掉 90% 的低级错误。
4.3 一个容易被忽略的性能细节
纵向扫描在"提前终止"这件事上做得很好，但有一个场景它反而不如横向扫描：当数组里第一个字符串特别长，而公共前缀又特别短的时候。比如["a" * 10000, "b"]，纵向扫描会在 col=0 就发现不匹配并返回，其实很快。真正慢的场景是公共前缀很长、但最后一个字符串在很靠后的位置才不匹配，这时候纵向扫描要扫很多列。不过这种情况横向扫描也一样慢，没有本质区别。
真正值得注意的性能点是：不要在循环里反复调用strs[i].size()。虽然std::string::size()是 O(1) 的，但把它提到循环外或者用引用缓存，在极端数据量下还是有意义的。我在上面的代码里没做这个优化，因为可读性优先，但如果你在打比赛追求极致，可以改成先算好每个字符串的长度存数组。
5. 进阶：分治解法与面试加分技巧
5.1 分治解法的完整实现
分治的思路是：把数组从中间劈成两半，分别求左半部分的最长公共前缀和右半部分的最长公共前缀，然后再求这两个前缀的公共前缀。递归下去，直到区间里只剩一个字符串，它的公共前缀就是它自己。
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; return divide(strs, 0, strs.size() - 1); } private: string divide(vector<string>& strs, int left, int right) { if (left == right) return strs[left]; int mid = left + (right - left) / 2; string lcpLeft = divide(strs, left, mid); string lcpRight = divide(strs, mid + 1, right); return commonPrefix(lcpLeft, lcpRight); } string commonPrefix(const string& a, const string& b) { int len = min(a.size(), b.size()); int i = 0; while (i < len && a[i] == b[i]) ++i; return a.substr(0, i); } };分治的复杂度同样是 O(S)，但它的常数比纵向扫描大，因为多了递归调用和字符串拷贝的开销。那为什么还要学它？因为面试官喜欢看你会不会分治。分治是一种通用的算法思想，能体现你对递归、区间划分、结果合并的理解。如果面试时你先写出纵向扫描，然后主动说"这题也可以用分治做，思路是……"，加分效果立竿见影。
5.2 二分查找解法的适用场景
二分查找的思路稍微绕一点：我们不逐个字符比较，而是二分"前缀的长度"。设最短字符串长度为 m，我们在[0, m]范围内二分长度 mid，然后验证所有字符串的前 mid 个字符是否都相同。如果相同，说明答案至少是 mid，往右半区继续找；如果不同，往左半区找。
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; int minLen = INT_MAX; for (const auto& s : strs) minLen = min(minLen, (int)s.size()); int lo = 0, hi = minLen; while (lo < hi) { int mid = lo + (hi - lo + 1) / 2; if (isCommonPrefix(strs, mid)) lo = mid; else hi = mid - 1; } return strs[0].substr(0, lo); } private: bool isCommonPrefix(vector<string>& strs, int len) { string prefix = strs[0].substr(0, len); for (int i = 1; i < strs.size(); ++i) { if (strs[i].substr(0, len) != prefix) return false; } return true; } };注意二分里的mid = lo + (hi - lo + 1) / 2，这个+1是为了避免死循环。当lo和hi相邻时，如果不加 1，mid会等于lo，而如果此时isCommonPrefix返回 true，lo = mid就原地踏步了。这是二分查找的经典陷阱，写的时候一定要想清楚"我要找的是最后一个满足条件的值"还是"第一个满足条件的值"，然后决定 mid 的取整方向。
二分法的时间复杂度是 O(S·log m)，比纵向扫描的 O(S) 差，所以实际并不推荐。但它的价值在于：当验证操作很昂贵时，二分能把线性验证变成对数次验证。这道题里验证很便宜，所以二分不划算；但如果换成"验证一个前缀是否是所有字符串的前缀"需要读磁盘或者走网络，二分就香了。理解这个 trade-off，比记住代码本身更重要。
5.3 面试时怎么讲这道题
如果面试官让你讲思路，我建议按这个顺序说：
- 先点明答案的上界是"最短字符串长度"，这是所有解法的共同出发点。
- 给出纵向扫描的思路，强调它代码短、天然处理边界、能提前终止。
- 主动提一句分治，说明它复杂度相同但能体现分治思想。
- 如果面试官追问优化，再聊二分，并解释为什么这题里二分不划算。
这个顺序的好处是：先给最实用的方案，再展示知识广度，最后展示你对复杂度 trade-off 的理解。比一上来就炫技写分治要稳妥得多。
6. 从这道题延伸出的字符串处理习惯
6.1 三个可以带走的通用习惯
刷这道题最大的收获，其实不是记住某段代码，而是养成几个处理字符串数组的通用习惯。
习惯一：先想边界，再写逻辑。拿到任何字符串题，先在纸上列出可能的边界输入：空数组、空串、单元素、全相同、全不同、答案等于最短串。列完再动手，能省下大量调试时间。
习惯二：访问二维逻辑时用 row/col 命名。字符串数组本质是字符矩阵，用row/col比i/j可读性高一个档次。这个习惯在写矩阵题、动态规划题时同样适用。
习惯三：越界检查永远放前面。只要涉及下标访问，先问自己"这个下标会不会越界"，把检查写在访问之前。C++ 的||短路特性可以帮你，但前提是你把检查放对了位置。
6.2 这道题还能怎么变
最长公共前缀这个模型，在实际工程里有很多变体。比如"找一组文件路径的公共目录前缀"，本质就是这道题，只不过分隔符从字符变成了/。再比如"找一组 DNA 序列的公共片段"，思路一样，只是匹配规则可能更复杂。还有"版本号比较"里的公共前缀提取，也是同一个套路。
我在实际项目里遇到过一次类似需求：要给一批日志文件按公共前缀分组，方便批量处理。当时用的就是纵向扫描的变体，先按最短文件名长度定上界，再逐列比较。代码不到二十行，但比正则表达式方案快了一个数量级。所以别小看这道简单题，它的模型迁移能力很强。
注意：迁移到实际场景时，要特别注意"前缀"的定义。文件路径的前缀通常以分隔符为界，不能简单按字符比较，否则
/abc和/abcd会被误判为有公共前缀/abc，但实际上它们是两个不同的目录。这种语义层面的坑，比代码层面的坑更隐蔽。
6.3 关于刷题节奏的一点个人体会
最后聊点题外话。像第 14 题这种"简单题"，很多人刷完就过，觉得没什么可总结的。但我的经验是，简单题才是打磨代码习惯的最佳素材。难题你光是想出思路就用光了精力，没空去抠命名、边界、可读性；简单题思路秒出，正好可以把注意力放在"怎么写得漂亮"上。
我现在回头看自己早期刷的题，那些当时觉得"太简单不值得记"的题，恰恰是后来面试里被追问细节最多的。面试官不会问你红黑树怎么旋转，但很可能会盯着你写的substr(0, col)问一句"这里为什么是 col 不是 col+1"。所以，把每一道简单题都当成一次代码审阅的机会，长期下来收益远超你的想象。
这道题我前后写过不下十遍，每次重写都会微调一点：有时候把越界检查抽成单独的函数，有时候试试用迭代器代替下标。不是为了炫技，而是为了保持手感。字符串处理是工程里最高频的操作之一，把这些基本功练到肌肉记忆，比多刷十道难题实在得多。
