刷力扣刷到第14题的时候，我一开始是有点不屑的——最长公共前缀，不就是拿第一个字符串当头，然后挨个比较嘛。但真正提交了两次之后，我才发现这道题里藏着的门道比想象中多。今天就把我对这道题的完整拆解、各种解法的思路和踩过的坑一次性写清楚。
力扣14题要求我们在一组字符串中找出最长公共前缀。换句话说，输入是一个字符串数组，输出是一个字符串，这个输出的字符串是数组中所有字符串的共同前缀，并且是最长的。如果不存在公共前缀，就返回空字符串。举个例子：["flower","flow","flight"]，公共前缀是"fl"；["dog","racecar","car"]，没有任何公共前缀，返回""。
1. 题意拆解：看似简单的字符串比较，为什么隐藏着算法思维
1.1 题目描述与示例
让我们先看一下题目细节。函数签名通常是string longestCommonPrefix(vector<string>& strs)，传入一个字符串数组，返回值是字符串。数组可能为空，也可能只有一个元素。只有一个元素时，最长公共前缀就是它本身。空数组则需要返回空字符串。这些边界条件在面试中经常被拿来考察候选人的思维缜密性。
示例一：输入["flower","flow","flight"]，输出"fl"。因为这三个字符串都有前缀"fl"，而"flo"不是"flight"的前缀，"fli"也不是"flower"的前缀，所以最长公共前缀只能是"fl"。示例二：输入["dog","racecar","car"]，输出""。因为没有任何一个字符是三个字符串共同拥有的前缀，直接返回空串。
这里有一个容易被忽略的点：前缀必须是连续的、从第一个字符开始的子串。也就是说，"flower"和"flow"的公共前缀是"flow"，但加上"flight"后，最长公共前缀被缩短为"fl"。所以求的是所有字符串的交集，不是两两之间的最长公共前缀后再取交集。这个交集运算的语义非常关键，很多人在实际写代码时，会把"当前公共前缀"与"下一个字符串"进行比较，但比较的对象不是求两个字符串的"最长公共前缀"那么直接，而是要保证当前前缀必须是下一个字符串的前缀，否则就不断缩短。
1.2 为什么这道题容易藏坑
这道题看似简单，但至少有三个地方容易出错：第一，对边界条件的处理，比如空数组、空字符串、只有一个字符串；第二，对"前缀"概念的理解，很多人会把子序列、子串混为一谈；第三，算法选择不当导致的性能问题，尤其是当输入规模很大或者字符串很长时，不同的解法可能差出一个数量级。
更关键的是，这道题虽然只是"简单"难度，却是很多复杂字符串算法的基础。比如字典树（Trie）的构建、IP地址最长前缀匹配、路由表查找，本质上都是在处理前缀关系。把这道题吃透，对于后续理解更高级的数据结构和算法有直接帮助。同时，这道题也非常适合用来练习"如何把边界条件处理干净"，因为它足够小、足够清晰，却又能展现代码风格和思维习惯。
2. 横向扫描：最直观的思路，但也最容易写出性能隐患
最符合直觉的做法，叫做横向扫描。我们先把第一个字符串当作"当前最长公共前缀"，然后拿它和第二个字符串比较，得到一个新的前缀，再拿这个新前缀和第三个字符串比较……依次类推，直到所有字符串都处理完，剩下的那个前缀就是答案。
这个过程像不像我们日常生活里几个人讨论一个共同话题？先听第一个人说，再听第二个人说，不断缩小共识范围，最后剩下的是所有人的共同点。横向扫描的每一步，都是在用当前共识去约束下一个对象。
2.1 核心思路与代码实现
横向扫描的逻辑用代码写出来很清晰：
string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; string prefix = strs[0]; for (int i = 1; i < strs.size(); ++i) { // 不断缩短prefix，直到它是strs[i]的前缀 while (strs[i].find(prefix) != 0) { prefix.pop_back(); if (prefix.empty()) return ""; } } return prefix; }这里用了find(prefix) != 0来判断prefix是不是strs[i]的前缀，它等价于strs[i].rfind(prefix, 0) == 0。在C++20里可以用starts_with(prefix)，更直观。在Python里对应startswith()，Java里是startsWith()。
每次比较时，如果当前前缀不是下一个字符串的前缀，就把最后一个字符删掉，再试探，直到变成前缀或者变成空串。之所以从后往前删，是因为前缀的缩短是单调的——一旦发现不匹配，更长的前缀肯定也不匹配，所以只需要逐步缩短。这个"单调性"是整个算法能够高效工作的根本保证。
2.2 复杂度分析与适用场景
横向扫描的时间复杂度是O(S)，S是所有字符串中字符数量的总和。最坏情况下，比如所有字符串都一样长且完全相同，那么每次比较都需要遍历整个prefix，总操作次数接近n*m，其中n是字符串个数，m是最长字符串长度。空间复杂度是O(1)，只用了常数个额外变量。
这种解法适合字符串数量不多、长度不长的情况。它的优势是直观、简单、不容易写错，而且不需要额外空间。但它的缺点是当第一个字符串特别长，而后面的字符串前缀很短时，会做很多无用的字符比较。比如第一个字符串长度是1000，第二个字符串是"a"，那么第一次比较就要从"a"开始不断缩短，最多删999次，每次都要执行find，虽然这个例子中find是常数级，但总操作次数仍然可能达到O(S)。
在实际面试中，横向扫描往往是第一个想到的方案，但如果面试官追问"能不能再优化"，我们就需要看看纵向扫描了。另外，如果使用C++的string::find，内部实现通常会优化得很好，但在多次调用时依然有函数调用开销。对于极致性能需求，可以考虑直接比较字符来减少开销。
3. 纵向扫描：从列的角度重新审视，平均性能更优
横向扫描是以字符串为单位，逐个更新公共前缀。纵向扫描则换了一个角度：我们同时比较所有字符串的同一位置字符，就像检查每一列是否相同。只要某一列出现了不一致，那么这一列之前的所有字符就是最长公共前缀。
3.1 逐列比较的思路
想象我们把所有字符串上下排列，每个字符串看作一行，那么问题就变成了从第一列开始，逐列检查每个位置上的字符是否全部相同。如果第j列的所有字符都相同，就把它加入答案；一旦发现某个字符串在第j列没有字符，或者字符与第一个字符串不同，就立即停止，答案就是第0到第j-1列的内容。
这种思路的好处是，它把"前缀"的语义直接映射到了"列"上——因为我们只关心所有字符串共同拥有的、从头开始的连续序列，所以列与列之间是独立的，不需要维护一个不断缩短的前缀字符串。从另一个角度看，纵向扫描其实是在并行比较所有字符串的对应位置，天然具有"早停"的特质：只要遇到第一处不一致，循环立刻结束。
3.2 代码实现与性能对比
纵向扫描的实现也很简洁：
def longestCommonPrefix(strs): if not strs: return "" # 以第一个字符串长度为基准 for i in range(len(strs[0])): c = strs[0][i] for j in range(1, len(strs)): # 如果当前字符串长度不够，或者字符不一致，直接返回 if i == len(strs[j]) or strs[j][i] != c: return strs[0][:i] return strs[0]注意这里有一个关键判断：i == len(strs[j])，表示第j个字符串在第i列已经不存在了，此时最长公共前缀只能到第i-1列。这个条件一定要放在取字符之前，否则会越界。
在最好情况下，比如第一个字符串很短，或者第二列就出现不匹配，纵向扫描只需要比较n个字符就能结束，时间复杂度O(n)。而横向扫描即使在最好情况下，至少也要遍历完整的第一个字符串来更新前缀，成本更高。最坏情况下纵向扫描同样要遍历所有字符串的所有字符，复杂度还是O(S)，但平均情况下纵向扫描通常会提前终止，所以实际表现往往优于横向扫描。
从空间复杂度看，纵向扫描也是O(1)。如果题目要求我们不能修改原数组，这也完全满足。我在实际测试中对比过两种解法，当字符串数量很多且前缀很短时，纵向扫描速度明显更快；但当字符串数量很少、前缀很长时，两者差距很小。所以如果要向面试官展现你的思考深度，纵向扫描是一个很好的进阶答案。
4. 分治与二分查找：两种进阶思路的对撞
在掌握基础解法之后，还有两道更有意思的进阶菜：分治法和二分查找法。这两种方法在面试中不常被要求当场写出来，但理解它们有助于加深对"前缀"问题的认识，而且它们背后的思想——拆分与合并、利用单调性——在很多工程场景中都是常用武器。
4.1 分治法的思路与实现
分治法的思想很简单：把字符串数组分成左右两半，分别求出左右两半的最长公共前缀，然后再求这两个前缀的公共前缀。递归地做下去，直到只剩下一个字符串。
比如有四个字符串，我们先把左边两个求出一个前缀L，右边两个求出一个前缀R，然后对L和R再做一次普通的前缀比较，得到最终答案。本质上，分治法把"多个字符串的公共前缀"拆成了若干个"两个字符串的公共前缀"问题，最后合并。
这里有一个值得注意的点：两个子问题各自的最长公共前缀，它们的公共前缀就是整体数组的最长公共前缀。这个性质是良定义的，因为前缀的交集满足结合律。用公式表达就是：lcp(s1..sn) = lcp(lcp(s1..sk), lcp(sk+1..sn))。
分治的代码框架如下：
public String longestCommonPrefix(String[] strs, int l, int r) { if (l == r) return strs[l]; int mid = (l + r) / 2; String leftLcp = longestCommonPrefix(strs, l, mid); String rightLcp = longestCommonPrefix(strs, mid + 1, r); return commonPrefix(leftLcp, rightLcp); } private String commonPrefix(String a, String b) { int i = 0; while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) { i++; } return a.substring(0, i); }时间复杂度同样是O(S)，但由于递归过程中每个字符最多被比较常数次，实际开销会略高于横向扫描。不过分治法的优势在于它天然适合并行化，在多线程或分布式环境下，可以同时计算多个分区的结果，再逐层合并，非常适合处理超大规模的字符串集合。
4.2 二分查找的妙用
二分查找法的思路更有趣：既然所有字符串的最长公共前缀长度不可能超过最短字符串的长度，那我们就可以在这个长度范围内进行二分查找。每次取一个中间长度mid，检查所有字符串的前mid个字符是否完全相同。如果相同，说明答案长度至少为mid，我们把下界移到mid；如果不同，说明答案长度小于mid，把上界移到mid-1。
这个方法的关键是利用了"前缀匹配的单调性"：如果长度为k的前缀是公共前缀，那么长度小于k的所有前缀也一定是公共前缀；反过来，如果长度为k的前缀不是公共前缀，那么长度大于k的所有前缀也一定不是公共前缀。所以我们可以用二分查找来穷举答案长度。
实现方式如下：
string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; int minLen = INT_MAX; for (const string& s : strs) minLen = min(minLen, (int)s.size()); int low = 0, high = minLen; while (low < high) { int mid = (low + high + 1) / 2; if (isCommonPrefix(strs, mid)) { low = mid; } else { high = mid - 1; } } return strs[0].substr(0, low); } 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].rfind(prefix, 0) != 0) return false; } return true; }这里二分查找的次数是O(log m)，其中m是最短字符串的长度。每次检查需要遍历所有字符串的前len个字符，所以总时间复杂度是O(S log m)，通常比横向扫描的O(S)要慢，但好处是它不会在字符串前缀已经明显很短时浪费太多操作。比如当最短字符串长度为1000，而实际公共前缀只有5时，二分查找大约只需要log2(1000)≈10次检查，每次检查可能提前失败，效率并不差。如果字符串数量非常大，二分查找的检查次数少，每次检查可以并行化，在某些场景下反而更优。
4.3 两种进阶方法的取舍
分治法和二分查找法各有适用区间。分治法适合字符串数组规模极大、需要并行计算的环境；二分查找法适合在"前缀长度未知但最短长度已知"的场景，且要求我们对答案的单调性敏感。
从代码简洁度上看，横向扫描和纵向扫描明显更受欢迎。力扣14题的标准答案也通常是这两种。但如果你能在面试中主动提出分治或二分，并能清晰解释复杂度，这会是加分项。我个人在准备面试时，会把这四种方法都写成代码，进行对比测试，这样即使被追问，也能从容应对。
5. 真实工程中的前缀匹配问题：从LeetCode到实际项目
刷题从来不只是为了面试。最长公共前缀这个算法，在真实工程里有着相当广泛的应用。理解这些场景，反过来也能加深对这道题的理解。
5.1 前缀匹配在路由系统中的应用
最典型的案例是网络路由中的最长前缀匹配。在IP路由表里，每一条路由规则都是一个IP前缀，比如192.168.0.0/16，表示前16位是网络号。当数据包到来时，路由器需要找到匹配目标IP的最长前缀路由，也就是在多个可匹配的前缀中，选择前缀长度最长的那一个。这比"最长公共前缀"更复杂——它要找的是字典中与给定IP匹配的最长前缀，而不是多个字符串的公共前缀。但底层思想一脉相承：对二进制串进行前缀比较，逐位匹配直到出现差异。
在实现路由查找时，通常会使用字典树（Trie）来加速，把每个IP地址的二进制位沿树往下走，遇到可行的路由节点就记录，最后记录的节点就是最长匹配项。这和力扣14题的纵向扫描思路其实很像——都是逐位检查所有可能的路径。
5.2 字典树（Trie）与自动补全
另一个直接相关的场景是自动补全和拼写检查。搜索框里的联想、IDE里的代码补全，它们背后的数据结构往往就是字典树。字典树的每个节点代表一个前缀，从根到任意节点的路径对应的字符串就是一组前缀。当我们输入"app"时，系统会顺着前缀路径找所有以"app"开头的单词，比如"apple"、"application"。
这道题和字典树的关系在于，求一组字符串的最长公共前缀，相当于在一棵字典树上找到最深的、拥有所有字符串所对应叶节点公共祖先的路径。如果你能理解力扣14题，再去看字典树的插入和查询，会轻松很多。
5.3 如何根据场景选择算法
在工程中，我们很少直接调用一个"最长公共前缀"函数来解决某个孤立问题。更多时候，它只是某个流程的环节。比如处理一批URL时，要提取它们的公共域名前缀；在分析日志时，要找出多行日志的公共起始格式；在数据压缩中，前缀匹配也是LZ算法的一部分。
这时，选择哪种算法取决于数据规模和实时性要求。如果字符串数量很少，直接用横向扫描就行；如果字符串数量很多、单个字符串很长，纵向扫描往往更可靠；如果还需要后续的增量式更新，比如不断插入新的字符串并动态维护公共前缀，那就需要考虑用字典树或线段树来支持更新操作，而不是每次全量重算。
我在做一个日志分析工具时，就遇到过需要批量比较数万条记录前缀的需求。一开始用横向扫描，结果发现最慢的环节反而是反复调用substr和字符串拼接。后来改成只记录前缀长度，最后一次性输出，性能提升了一个数量级。这也是一个很重要的经验：思考问题时，多想想能不能用下标和长度来替代实际字符串操作，很多性能瓶颈都能因此化解。
6. 边界条件与常见错误：那些让我提交失败的坑
即使解法思路正确，仍然有不少人会提交失败。这一节我把自己踩过的坑和见过的错误集中梳理一遍，希望后来者少走弯路。
6.1 空数组与空字符串的陷阱
第一个坑是空数组。如果输入是[]，那么不存在任何字符串，公共前缀显然是空字符串。但很多人会忽略这一步，直接取strs[0]，导致越界异常。因此几乎所有解法，第一步都必须是判空。
第二个坑是数组中包含空字符串。比如["", "abc"]，第一个字符串是空串，它与任何字符串的公共前缀都是空串，最终结果也是空串。在横向扫描中，如果prefix一开始就是空串，进入循环后会很快返回；在纵向扫描中，第一个字符串长度为0，直接返回空串。这个判断同样不能少。
6.2 索引越界与指针更新问题
纵向扫描最容易犯的错误是忘记检查当前字符串的长度是否足够。比如遍历到第5列时，如果某个字符串只有4个字符，那么访问strs[j][5]就会越界。正确的顺序是：先判断i是否等于strs[j].length()，再取字符比较。类似地，在横向扫描中，如果使用find或者startWith，就不会出现越界问题，因为语言自带的API封装好了边界检查。但如果你自己写循环判断字符是否相等，就必须小心。
还有一个容易被忽视的坑是：横向扫描中，当prefix缩短到空串时，应该立即返回，而不是继续循环。虽然继续循环最终也会得到空串，但提前返回可以避免无意义的比较。有些编译器在没有开启优化时，会多执行很多次循环体。
6.3 大小写与Unicode的额外思考
力扣默认的测试用例只涉及小写字母，但实际应用中，前缀匹配可能涉及大小写敏感、数字、符号甚至Unicode字符。比如比较"Apple"和"apply"时，如果要求大小写不敏感，我们需要先统一转换为小写再比较；如果涉及中文，虽然字符串在底层是字节数组，但按字符比较时要注意编码方式。在C++中，std::string按字节存储，一个UTF-8中文占3个字节，直接按下标比较可能会把同一个字符的不同字节拆开比较，导致错误结果。此时需要考虑使用宽字符或者按码点比较。
我自己曾在处理多语言文本时，就因为没注意UTF-8的变长编码，导致公共前缀算出了一个乱码。后来把所有字符串先转成统一的Unicode表示，才解决问题。所以在工程实践中，永远不要假设字符串只包含ASCII字符。
除了这些边界条件，我还有一个体会：这道题虽然简单，但非常适合用来练习"如何写出无懈可击的代码"。每次提交前，我都会在脑海中模拟几个特殊输入：空数组、空字符串、单个字符串、所有字符串完全相同、第一个字符串特别短、最后一个字符串特别短……逐个确认代码能正确处理。养成这个习惯后，我提交算法题的通过率提升了很多。
7. 最后的实践建议
7.1 四种解法的记忆点
横向扫描是"拿第一个字符串当基准，依次和后面的字符串求公共前缀"；纵向扫描是"同时看所有字符串的第i列，遇到不一致就停止"；分治法是"递归拆两半，再合并两个子答案"；二分查找法是"对答案长度做二分，用前缀检查当判定函数"。这四个思路分别对应了迭代更新、逐列检查、分而治之、二分枚举四种算法范式。
如果你想快速记住它们，可以这样类比：横向扫描是"逐个谈话，不断修正共识"；纵向扫描是"集体检查每一行，直到有人出列"；分治是"分组讨论，再把组长们的结论汇总"；二分是"猜一个长度，验证是否成立，再调整猜测范围"。
7.2 给后来者的三条建议
第一，刷题时不要只满足于一种解法。拿这道题来说，四种方法都写一遍，比刷十道同质化的题更有价值。每次写完后，随机生成几组测试数据，对比运行时间，你会对复杂度有更直观的感觉。
第二，时刻保持对边界条件的敏感。很多看起来"简单"的题，真正的考点就是边界处理。我面试别人时，也经常用这道题当开场题，因为从候选人是否检查空数组、是否处理单元素数组，就能快速判断其工程素养。
第三，把算法和实际场景联系起来。最长公共前缀不是孤立的知识点，它和IP路由、字典树、自动补全、数据压缩都有千丝万缕的联系。每次刷完题，想一想这个算法在现实世界中可能出现在哪里，记忆会深刻得多。
希望这篇关于力扣14题的拆解能帮到你。如果你有自己的独特解法，或者在刷题中遇到过什么有趣的问题，欢迎一起交流。
