LeetCode最长公共前缀四种解法：从横向扫描到二分查找

LeetCode热题100里最长公共前缀原题第14题绝对是我见过最“反差萌”的一道题。名字听着像个easy题看一眼题干给定一个字符串数组找出这些字符串的最长公共前缀没有就返回空字符串。很多人的第一反应是这不就是个两重循环的事吗但当我把四种解法都刷了一遍之后才发现这道题把字符串处理、边界控制、分治思想、二分思想全串起来了做一道题的收获抵得上瞎刷十道。这道题适合所有在刷LeetCode的人尤其是刚开始撸热题100的同学。它看起来简单实际上对循环边界的敏感度要求很高很多新手会在“字符串越界”这个点上栽跟头。这篇就按我实际刷题的过程从题干定义、四种解法、复杂度对比到边界测试完整梳理一遍希望看完你能把这道题吃得透透的。1. 题目到底在问什么先吃透最长公共前缀的定义1.1 题干和基本判定逻辑LeetCode第14题的完整描述是编写一个函数来查找字符串数组中的最长公共前缀如果不存在公共前缀返回空字符串。官方给了两个示例strs [flower, flow, flight]输出fl因为这三个字符串从头开始重合的部分就是fl。strs [dog, racecar, car]输出因为第一个字符就互不相同公共前缀为空。这里有一个最容易被忽略、却最关键的点公共前缀一定是从每个字符串的第0位开始连续匹配的。它不是子序列不是子串里最长的那段而是所有字符串从开头逐字符对齐后共同拥有的那一小段。换句话说只要某个字符串的第k位和对齐位置不同那么长度为k1及以后的所有可能性全部作废。很多人会把这道题和“最长公共子串”搞混。前者要求从头对齐后者不要求位置一致前者用扫描思路几行就写完后者得上动态规划。题目名里的“前缀”两个字就是最大的提示。还有一个隐含的细节返回的公共前缀本身必须是某个字符串的前缀。当所有字符串完全相同或者只有一个字符串时最长公共前缀就是整个字符串本身。所以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 变形题与后续学习建议最长公共前缀做熟之后有几个变形和延伸可以顺手刷掉对巩固很有帮助字符串数组找最长公共后缀把每个字符串反转再用最长公共前缀的解法最后把结果反转回来。能理解这个转化说明你掌握了复用的思路。多个字符串的字典序最小前缀结合排序先排字典序再比较第一个和最后一个字符串的公共前缀这其实是另一种利用排序性质解题的思路。前缀匹配的进阶字典树TrieLeetCode的实现Trie前缀树就是这道题的最终进化版。把字符串逐个插入字典树从根节点开始往下走直到遇到分叉节点走过的路径就是最长公共前缀。字典树适合处理大量字符串的前缀查询在自动补全、拼写检查场景里很常见。如果时间有限我的建议是先吃透横向和纵向扫描然后把分治和二分各写一遍最后再看一眼字典树解法。这样由浅入深既掌握了热题100的必考答案也顺手预习了更进阶的数据结构。6.2 我的实操心得和踩坑记录最后说点个人经验。我在LeetCode上第一次提交这道题时用的就是最普通的横向扫描但犯了个低级错误没有判断空数组。结果strs[0]直接IndexError红了一大片。后来每次写字符串类题目我第一行必写边界判断已经成本能了。纵向扫描的越界判断也是重灾区。j len(strs[i])或strs[i][j]的顺序写反或者漏掉长度判断都会在测试用例[ab, a]上报错。调试这类问题的时候别急着看完整的错误堆栈先用最简单的两个字符串的用例排查定位效率高很多。还有一个经验是关于刷题节奏的。热题100里的easy题AC不是终点把题解区的高票答案全部过一遍才是真正的收获。最长公共前缀这题尤其如此只看一种解法你会觉得题目很平淡但当你把横向、纵向、分治、二分四种解法都写一遍你对“同一个问题可以有多种切入角度”这件事的体感会完全不一样。以后再碰到hard题就不会只困在第一个想法里出不来。我在实际面试别人时最长公共前缀这道题也常被用作热身题。我观察到的现象是能写出横向扫描的候选人占大多数能把纵向扫描的越界讲清楚的少一些主动提到分治或二分的凤毛麟角。所以如果你已经看到这里其实你已经比绝大多数刷题者多想了一层。这道题的价值不在于你背下几种解法而在于你通过它建立起来的边界意识和多角度思考习惯这些才是刷LeetCode真正能沉淀下来的东西。