刷力扣刷到第14题的时候我一开始是有点不屑的——最长公共前缀不就是拿第一个字符串当头然后挨个比较嘛。但真正提交了两次之后我才发现这道题里藏着的门道比想象中多。今天就把我对这道题的完整拆解、各种解法的思路和踩过的坑一次性写清楚。力扣14题要求我们在一组字符串中找出最长公共前缀。换句话说输入是一个字符串数组输出是一个字符串这个输出的字符串是数组中所有字符串的共同前缀并且是最长的。如果不存在公共前缀就返回空字符串。举个例子[flower,flow,flight]公共前缀是fl[dog,racecar,car]没有任何公共前缀返回。1. 题意拆解看似简单的字符串比较为什么隐藏着算法思维1.1 题目描述与示例让我们先看一下题目细节。函数签名通常是string longestCommonPrefix(vectorstring 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(vectorstring 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。在C20里可以用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(sk1..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(vectorstring 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(vectorstring 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题的拆解能帮到你。如果你有自己的独特解法或者在刷题中遇到过什么有趣的问题欢迎一起交流。