最长公共前缀算法详解：纵向扫描与横向扫描两种解法

1. 从“找茬”游戏到算法问题最长公共前缀的直观理解如果你玩过“找茬”游戏或者对比过两份相似的文档那你其实已经接触过“最长公共前缀”这个概念的核心。想象一下你面前有三份手写的单词列表flower,flow,flight。你的任务是找出它们开头最长的、完全相同的那部分字母序列。从左到右一个个字母看过去f 都一样l 也一样到了第三个字母o,o,i——不一样了。那么它们共同的开头也就是最长公共前缀就是fl。这就是 LeetCode 第 14 题 “Longest Common Prefix” 要我们解决的问题。它看似简单却是面试中检验候选人基础编码能力、边界条件处理以及算法思维的经典入门题。很多朋友觉得这题太“小儿科”直接上手就写结果在诸如空数组、单字符串、或前缀完全包含等边界情况上栽了跟头。今天我们就抛开浮躁用两种截然不同但都极具代表性的解法配上详细的图解和代码拆解把这道题里里外外摸个透。无论你是刚开始刷题的新手还是想巩固基础的老手相信这篇深入的分析都能让你有所收获。2. 解法一纵向扫描——最符合直觉的“逐个击破”法第一种解法我们称之为“纵向扫描”。它的思路非常直接模拟的就是我们人眼比较的过程把所有字符串像士兵一样排成一列然后你作为指挥官从第一个位置索引0开始依次检查每一列上的“士兵”字符是否完全相同。2.1 算法步骤拆解与图解我们以字符串数组strs [flower, flow, flight]为例。第一步确立扫描范围和基准。我们选择第一个字符串flower作为基准。公共前缀不可能比任何一个字符串都长所以最长公共前缀的长度最多也就是这个基准字符串的长度。我们的扫描将从第0列第一个字符开始直到基准字符串的末尾或者直到发现某一列字符不一致为止。第二步开始纵向扫描。我们用一个外层循环i来表示当前正在检查的列索引字符位置。i 0检查所有字符串的第0个字符。strs[0][0]是fstrs[1][0]是fstrs[2][0]是f全部相同继续。i 1检查所有字符串的第1个字符。strs[0][1]是lstrs[1][1]是lstrs[2][1]是l全部相同继续。i 2检查所有字符串的第2个字符。strs[0][2]是ostrs[1][2]是ostrs[2][2]是i发现不同o和i不相等。第三步截取结果。扫描在i 2时终止。那么最长公共前缀就是从基准字符串flower的开头截取到第i位但不包括i也就是strs[0].substring(0, i)即fl。这个过程可以用下面的表格来可视化字符串索引 0索引 1索引 2索引 3...flowerflow...flowflow...flightflig...本列是否一致✅✅❌(停止检查)2.2 代码实现与逐行分析理解了思路我们来看 Java 实现。关键在于处理好各种边界条件。public String longestCommonPrefix(String[] strs) { // 边界情况1输入数组为空 if (strs null || strs.length 0) { return ; } // 以第一个字符串作为扫描的基准和长度参考 String firstStr strs[0]; int count strs.length; // 遍历第一个字符串的每一个字符位置 for (int i 0; i firstStr.length(); i) { char c firstStr.charAt(i); // 获取基准字符串在当前列的字符 // 遍历数组中其他字符串与基准字符进行比较 for (int j 1; j count; j) { // 边界情况2当前字符串长度不足或者字符不匹配 // 条件 i strs[j].length() 意味着其他字符串已经“到头了” if (i strs[j].length() || strs[j].charAt(i) ! c) { // 发现不一致或越界立即返回当前已确认的共同前缀 return firstStr.substring(0, i); } } } // 边界情况3第一个字符串本身就是整个数组的公共前缀 return firstStr; }逐行逻辑与避坑点分析空数组处理 (if (strs null || strs.length 0))这是防御性编程的基本功。如果输入就是空的自然没有公共前缀直接返回空字符串。很多线上判题系统会包含这个测试用例。基准选择我们选择strs[0]作为遍历的参照物。这里隐含了一个假设公共前缀一定以strs[0]开头。这显然是成立的因为公共前缀是所有字符串的共同开头。外层循环for (int i 0; i firstStr.length(); i)i代表当前比较的字符索引。循环的终止条件是i达到第一个字符串的长度。这意味着公共前缀最长也不会超过第一个字符串。内层循环for (int j 1; j count; j)j从 1 开始因为我们不需要让strs[0]自己和自己比较。这个循环的任务是检查其他所有字符串在第i位上的字符是否和基准字符c一致。核心判断条件if (i strs[j].length() || strs[j].charAt(i) ! c)这是本解法的精髓也是容易出错的地方。i strs[j].length()这个条件检查当前遍历的字符串strs[j]是否已经“不够长”了。例如数组是[ab, a]当i1时基准字符串ab有第二个字符b但a的长度为1索引1已经越界。此时公共前缀只能是a。必须先检查长度再取字符否则会触发StringIndexOutOfBoundsException。strs[j].charAt(i) ! c如果长度足够则直接比较字符是否相等。这两个条件任意一个满足都意味着公共前缀的查找应该终止。返回结果return firstStr.substring(0, i)当在某一列发现不匹配或越界时i恰好指向了第一个不匹配的字符索引。因此公共前缀就是firstStr从 0 到i-1的子串即substring(0, i)。substring方法的第二个参数是结束索引不包括所以用i正好。循环结束后的返回return firstStr如果整个外层循环都顺利执行完毕意味着第一个字符串的每一个字符都成功通过了所有其他字符串的检验。这说明第一个字符串本身就是整个数组的公共前缀。例如输入[abc, abc, abc]最终就会返回abc。2.3 复杂度分析与适用场景时间复杂度O(S)其中 S 是所有字符串中字符的总数。在最坏情况下所有字符串都相同且较长我们需要比较 S 个字符。空间复杂度O(1)我们只使用了常数级别的额外空间几个变量。纵向扫描法的优点是直观、易于理解和实现在大多数情况下尤其是字符串数组规模不大、字符串长度差异明显时效率很高。它的缺点在于如果数组的第一个字符串非常长而公共前缀其实很短我们仍然需要遍历完第一个字符串的很多字符才能在内层循环中由其他较短的字符串触发终止条件。不过在平均情况下这依然是一个优秀且可靠的解法。3. 解法二横向扫描——巧妙的“两两归约”法第二种解法我们称之为“横向扫描”或者更形象地叫它“两两归约”法。它的思路不是同时比较所有字符串的同一列而是像“擂台赛”一样让字符串两两比拼逐步缩小公共前缀的范围。3.1 算法思想与过程演示思路的核心是最长公共前缀 (LCP) 满足结合律。即LCP(S1, S2, ..., Sn) LCP(LCP(LCP(S1, S2), S3), ..., Sn)也就是说我们可以先求出前两个字符串的公共前缀prefix然后将这个prefix与第三个字符串求公共前缀得到一个新的、更短或不变的prefix再与第四个字符串求依次类推直到遍历完所有字符串。最终的prefix就是整个数组的公共前缀。还是以strs [flower, flow, flight]为例初始化prefix strs[0] flower。将prefix与strs[1] flow求公共前缀比较flower和flow从头开始逐个字符比对直到o和w不同实际上在索引4位置flower是eflow是w但更早地在索引2之后flow就结束了所以以短者为准。得到公共前缀flow。更新prefix flow。将prefix与strs[2] flight求公共前缀比较flow和flight。第一个字符f相同第二个字符l相同第三个字符o和i不同。得到公共前缀fl。更新prefix fl。数组遍历完毕最终prefix fl即为答案。这个过程可以看作prefix被不断地“修剪”直到适配所有的字符串。3.2 代码实现与关键函数横向扫描的代码通常包含一个辅助函数用于求两个字符串的公共前缀。public String longestCommonPrefix(String[] strs) { // 边界情况处理 if (strs null || strs.length 0) { return ; } // 初始化前缀为第一个字符串 String prefix strs[0]; // 从第二个字符串开始依次与当前前缀进行“两两归约” for (int i 1; i strs.length; i) { prefix commonPrefixBetweenTwo(prefix, strs[i]); // 一个小优化如果某次归约后前缀已经为空可以提前结束 if (prefix.isEmpty()) { break; } } return prefix; } // 辅助函数求两个字符串 str1 和 str2 的最长公共前缀 private String commonPrefixBetweenTwo(String str1, String str2) { // 确定比较的最小长度避免越界 int minLength Math.min(str1.length(), str2.length()); int index 0; // 逐个字符比较直到发现不同或达到较短字符串的长度 while (index minLength str1.charAt(index) str2.charAt(index)) { index; } // 返回从0到index不包括index的子串 return str1.substring(0, index); }代码要点与对比分析核心驱动逻辑主函数longestCommonPrefix的循环清晰地体现了“归约”思想。prefix作为一个动态更新的状态依次与数组中的每个元素交互。辅助函数的设计commonPrefixBetweenTwo函数职责单一只负责比较两个字符串。它通过while循环找到第一个不匹配的索引index。这里同样需要注意循环条件中index minLength要放在前面以防止在字符相等判断时发生越界。提前终止优化在主循环中一旦prefix被归约为空字符串那么它与后续任何字符串的公共前缀都将是空串。此时可以立即break跳出循环节省不必要的计算。这是一个很好的实践。与纵向扫描的对比思维角度纵向是“齐头并进”横向是“依次消化”。性能特点横向扫描的性能在某种程度上取决于输入数组的顺序。如果最短的字符串或差异性最大的字符串排在前面prefix会很快被缩短从而减少后续比较的次数。反之如果前几个字符串都很长且相似prefix的收敛速度会慢一些。但它的最坏时间复杂度与纵向扫描相同。代码结构横向扫描由于拆分了函数结构可能更清晰一些模块化更好。3.3 复杂度分析与另一种视角时间复杂度O(S)其中 S 是所有字符串中字符的总数。在最坏情况下例如所有字符串都相同我们需要比较所有字符。每次调用commonPrefixBetweenTwo的成本与当前prefix和待比较字符串的长度相关但所有比较的字符总数上限仍然是 S。空间复杂度O(1)。除了输入数组和几个变量我们只需要存储不断变化的prefix。虽然substring可能产生新的字符串对象但在复杂度分析中通常不考虑输出所占用的空间。横向扫描法提供了一种不同的解题视角它强调了问题的“可分解性”和“状态传递”。在解决更复杂的、具有重叠子问题特性的问题时这种“化整为零、逐步求解”的思想是动态规划等高级算法的基础。4. 边界条件与极端案例的深度剖析无论是哪种解法健壮性都体现在对边界条件和极端案例的处理上。下面我们系统地梳理一下并看看我们的代码是如何应对的。4.1 空数组或 null 输入这是最基本的防御。代码开头通过if (strs null || strs.length 0)进行判断直接返回。如果不处理后续访问strs[0]会导致NullPointerException或ArrayIndexOutOfBoundsException。4.2 数组中只有一个字符串例如strs [apple]。此时这个字符串自身就是其公共前缀。纵向扫描内层循环for (int j 1; j count; j)由于count1条件j 1不成立循环体一次都不会执行。外层循环结束后直接执行最后的return firstStr返回apple。横向扫描主循环for (int i 1; i strs.length; i)同样因为strs.length1而不执行直接返回初始化的prefix即apple。 两种解法都能正确返回。4.3 存在空字符串例如strs [, abc, ab]。公共前缀只能是空字符串。纵向扫描基准字符串firstStr是长度为0。外层循环for (int i 0; i firstStr.length(); i)的条件i 0一开始就不满足循环体不会执行直接跳到最后的return firstStr返回。横向扫描初始prefix 。第一次与abc求公共前缀commonPrefixBetweenTwo(, abc)中minLength 0while循环不执行返回。后续即使有优化判断if (prefix.isEmpty())也会提前跳出。最终返回。4.4 公共前缀恰好是某个字符串本身例如strs [abc, abcde, abcdef]。公共前缀是abc它是第一个字符串的全部。纵向扫描在比较第三个字符串abcdef时当i3对应字符d基准字符串abc的长度为3此时i firstStr.length()外层循环结束。循环结束后执行return firstStr返回abc。注意这里不是通过内层循环的if条件返回的而是自然结束循环后返回的。横向扫描prefix依次与abcde和abcdef归约结果都是abc。4.5 字符串长度差异巨大例如strs [a, ab, abc, abcd, abcdefghijklmn]。公共前缀是a。纵向扫描以a为基准长度仅为1。在i0比较完所有字符串的第一个字符a后i自增为1。下一次循环条件i firstStr.length()即1 1不成立循环结束返回firstStr即a。这里高效地利用了短字符串作为基准的优势。横向扫描prefix从a开始与后续字符串归约结果始终保持为a。关键心得处理字符串索引时“先检查长度再访问字符”是铁律。无论是i strs[j].length()的判断还是while (index minLength ...)中条件的顺序都是为了杜绝StringIndexOutOfBoundsException。这是此类题目最常见的运行时错误来源。5. 解法延伸与思维拓展分治法与二分查找虽然纵向和横向扫描已经足够解决本题但了解更多的思路有助于开拓算法思维。这里简要提两种更高级的解法。5.1 分治法递归的优雅分治法的思想是把大问题拆成小问题解决小问题再合并结果。对于本题我们可以将字符串数组分成两半分别找出左半部分的 LCP 和右半部分的 LCP然后再求这两个 LCP 的公共前缀。public String longestCommonPrefix(String[] strs) { if (strs null || strs.length 0) return ; return divideAndConquer(strs, 0, strs.length - 1); } private String divideAndConquer(String[] strs, int left, int right) { // 递归基如果只有一个字符串它就是自己的LCP if (left right) { return strs[left]; } // 分计算中间索引将问题分成两个子问题 int mid left (right - left) / 2; String lcpLeft divideAndConquer(strs, left, mid); String lcpRight divideAndConquer(strs, mid 1, right); // 治合并两个子问题的解 return commonPrefixBetweenTwo(lcpLeft, lcpRight); } // 复用之前的 commonPrefixBetweenTwo 函数 private String commonPrefixBetweenTwo(String str1, String str2) { ... }分析分治法的时间复杂度也是 O(S)但递归调用会带来额外的栈空间开销空间复杂度为 O(m log n)其中 m 是字符串平均长度n 是数组长度。在本题中分治法显得有点“杀鸡用牛刀”但它展示了如何将一个问题递归分解是理解更复杂分治算法如归并排序的好例子。5.2 二分查找法对前缀长度进行优化这是一种非常巧妙的优化思路。我们不去逐个字符比较而是直接猜测公共前缀的长度。因为公共前缀的长度一定在 0 到minLen所有字符串中最短的长度之间。我们可以在这个范围里进行二分查找。找到数组中最短字符串的长度minLen。设定查找范围low 0,high minLen。当low high时计算中间长度mid (low high) / 2。检查所有字符串的前mid个字符是否都相同。我们可以取第一个字符串的前mid位作为候选前缀prefix然后检查其他字符串是否都以这个prefix开头。如果都相同说明公共前缀长度至少为mid可以尝试更长的令low mid 1。如果不全相同说明公共前缀长度小于mid令high mid - 1。最终公共前缀的长度就是(low high) / 2或者high循环结束后的值取第一个字符串的相应子串即可。分析二分查找法将字符比较的次数从 O(S) 降低到了 O(S * log m)其中 m 是最短字符串长度。当字符串非常长时这种方法有优势。但它需要额外的startsWith或子串比较操作常数因子可能较大且代码实现稍复杂。对于本题的常规数据范围纵向/横向扫描通常更简单高效。6. 实战中的技巧与常见“坑点”复盘刷题不只是为了通过更是为了在实战中不出错。结合这道题我总结了几条宝贵的经验。1. 永远优先处理输入为空的边界情况。这是一个成本极低但收益极高的习惯。在函数开头加上if (strs null || strs.length 0) return ;能避免大量的潜在崩溃。面试中主动提及并处理这种情况能体现你思维的严密性。2. 字符串索引操作长度检查必须先行。无论是charAt(i)还是substring在涉及索引i时必须首先确认i没有超过字符串的length()。if (i str.length() || ...)这个条件顺序不能颠倒。我早期就曾因为写成if (str.charAt(i) ! c || i str.length())而遭遇惨痛的StringIndexOutOfBoundsException。3. 理解substring方法的参数含义。String.substring(beginIndex, endIndex)返回的是[beginIndex, endIndex)左闭右开区间的子串。当我们发现第一个不匹配的索引是i时公共前缀的结束索引正是i所以用substring(0, i)恰到好处。如果误写成substring(0, i-1)在i0即第一个字符就不匹配的情况下会出错。4. 选择最清晰的解法作为首选。在面试或竞赛中纵向扫描法通常是这道题的首选答案。因为它逻辑直白边界条件容易处理代码简洁不易出错。在时间有限的情况下写出一个正确、鲁棒的解法比追求一个理论上更优但实现复杂的解法更重要。横向扫描作为第二种思路可以用来展示你对问题的不同理解。5. 测试用例的设计。自己练习时要有意识地覆盖这些边界[](空数组)[](包含空串)[a](单元素)[, b](空串与其他)[abc, ab, a](前缀逐级缩短)[abc, abc, abc](完全相同)[dog, racecar, car](没有公共前缀)[flower, flow, flight](标准案例) 覆盖这些用例并通过你的代码健壮性就有了基本保障。回过头看“最长公共前缀”这道题就像一面镜子它照出的不是复杂的算法而是程序员扎实的基本功和严谨的思维习惯。把简单的题目做对、做稳其价值不亚于攻克一道难题。希望这两种解法及其背后的思考能帮助你更从容地面对此类基础且重要的字符串问题。