昨天有同学问我LeetCode 14“最长公共前缀”这道题是不是背个标准答案就完事了。我说如果只背答案那这道题你等于白刷。最长公共前缀是字符串算法里最基础的题目之一一句话描述场景却能在边界条件上卡住一大批人。它表面上只要求返回字符串数组中所有字符串共同的前缀但实际做起来横向扫描、纵向扫描、分治、二分、排序、甚至字典树都能扯出一串东西。这篇文章我就从一个刷题老油条的角度把两种主流解法掰开揉碎讲清楚再聊聊各种“优化思路”的真实价值最后把易错点和复杂度口径也一起整理出来。1. 题目先读懂边界条件比解题方法更值钱1.1 题面拆解到底哪个“前缀”才算数题目描述很简短编写一个函数查找字符串数组中的最长公共前缀如果不存在公共前缀返回空字符串。这里的关键词是“前缀”不是“子串”更不是“公共部分任意出现”。前缀要求从每个字符串的第一个字符开始连续截取的一小段。比如[flower,flow,flight]这三个字符串共同的前缀是fl不是flow因为flight没有flow这一段也不是f因为f虽然大家都满足但它不是最长的。很多人一上来就去找“最长的相同片段”那是把这道题和“最长公共子串”搞混了。最长公共子串允许片段出现在字符串中间问题难度会立刻上升解法可能涉及动态规划和后缀数组而公共前缀因为强制从开头对齐所以才有高效的线性扫描解法。面试官考这道题不是考你会不会动态规划而是考你有没有理解前缀的含义以及你能不能把循环边界处理干净。1.2 输入输出示例与隐含场景先看几个容易踩的输出用例[]应返回一个空字符串不可能提供任何公共前缀。[a]应返回a只有一个字符串时它本身就是最长公共前缀。[abc,abc,abc]应返回abc完全相同的字符串公共前缀就是整个字符串。[dog,racecar,car]应返回首字母就不一样公共前缀为空。空数组[]应该返回注意这里如果直接取strs[0]会抛空指针或数组越界异常。LeetCode 的输入一般不会出现数组元素为null的情况但工程上做防御性编程时还要考虑strs[i]为null的情况。我的习惯是只要发现任意一个字符串为null或为空串立刻返回因为空字符串和任何字符串的公共前缀都是空。这个思路能帮你少处理逻辑分支。1.3 这道题在面试里的潜台词它经常作为热身题出现面试官真正想看的是你会不会先问清楚输入约束能不能区分空数组和空字符串能不能说清楚时间复杂度和空间复杂度有没有准备多种思路很多人 5 分钟背完答案就以为会了面试官把题目改成“返回所有字符串中最长公共后缀”马上就懵了。其实公共后缀只要把每个字符串反转一下就又是一个公共前缀问题。这说明基础思路比答案本身重要。接下来我按横向、纵向两条主线展开再补充三种常见的优化路径。2. 解法一横向扫描拿公共前缀一轮一轮去“碰”2.1 思路把数组里的字符串两两取交集横向扫描的核心是维护一个“当前公共前缀”prefix。初始时令prefix strs[0]然后用它和strs[1]比较得到二者的公共前缀并赋值给prefix再拿新的prefix和strs[2]比较以此类推。这里有一个关键规律prefix只会变短绝不会变长。因为公共前缀是所有已比较字符串的共同部分每引入一个新字符串共同部分只可能被进一步截断。这个思路很像报名表逐张核对先拿第一张表的开头和第二张表比对留下共同部分再拿共同部分和第三张表比对一直到最后一张留下的就是所有人的共同开头。2.2 Java 实现逐字符比较版我推荐先写逐字符比较版本因为逻辑最透明class Solution { public String longestCommonPrefix(String[] strs) { if (strs null || strs.length 0) { return ; } String prefix strs[0]; for (int i 1; i strs.length; i) { int j 0; while (j prefix.length() j strs[i].length() prefix.charAt(j) strs[i].charAt(j)) { j; } if (j 0) { return ; } prefix prefix.substring(0, j); } return prefix; } }逐行解释一下外层循环从第二个字符串开始每一轮都重新计算prefix和strs[i]的公共前缀长度j。while里有三个条件缺一不可下标j不能超过prefix的长度不能超过当前字符串的长度同时对应位置的字符必须相等。如果j 0说明当前字符串的第一个字符就和prefix对不上整个数组不可能有公共前缀直接返回空串。prefix.substring(0, j)取的是[0, j)刚好是已确认的前缀。也有一种更短的写法用indexOf判断前缀是否存在for (int i 1; i strs.length; i) { while (strs[i].indexOf(prefix) ! 0) { prefix prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) return ; } }这种写法看起来简洁但内部indexOf可能做模式匹配并不一定比逐字符快而且频繁substring会创建新字符串。我更建议用逐字符版理解问题用短写法展示面试时的编码速度。2.3 复杂度与分析设所有字符串的字符总数为 S最坏情况是所有字符串完全一样长度为m数量为n那么每次比较都要从第一个字符一直比到最后一个字符共进行n-1轮总比较次数约等于(n-1)*m也就是 O(S)。空间上只有prefix和若干下标辅助空间 O(1)。横向扫描的缺点是存在重复比较如果第一个字符串是aaaaaaaaaaab第二个是aaaaaaaaaaac第三个是aaaaaaaaaaad那么每一轮都要从头开始比较一大段相同的前缀aaaaaaaaaaa这个前缀其实前一轮已经确定过了白白浪费了比较机会。这也是我接下来讲纵向扫描的动机。3. 解法二纵向扫描从第一列开始逐个对齐3.1 思路一次性比较所有字符串的同一列纵向扫描不维护一个不断缩短的prefix而是从第 0 列开始先取strs[0].charAt(i)作为基准再依次检查数组里其余所有字符串的第i个字符是否等于这个基准。如果这一列全都相等进入下一列只要发现某个字符串已经到末尾或者第i个字符不相等就返回strs[0]的前i个字符。打个比方一群人站成一排你喊“看第一列”所有人同时亮出第一个字符必须完全一样才进入下一列。一旦某一列出现不同前面已经通过的列就是答案。3.2 Java 实现与边界处理class Solution { public String longestCommonPrefix(String[] strs) { if (strs null || strs.length 0) { return ; } for (int i 0; i strs[0].length(); i) { char c strs[0].charAt(i); for (int j 1; j strs.length; j) { if (i strs[j].length() || strs[j].charAt(i) ! c) { return strs[0].substring(0, i); } } } return strs[0]; } }需要注意三个地方外层循环以strs[0].length()为上限因为公共前缀不可能超过第一个字符串的长度。内层循环从j 1开始因为第0个字符串的当前字符就是基准c。判断语句里i strs[j].length()必须写在charAt(i)之前否则当字符串已经走到末尾时再访问charAt(i)会抛IndexOutOfBoundsException。这个顺序是纵向扫描最容易出错的地方。当发现第i列不匹配时返回strs[0].substring(0, i)注意不包含i因为第i列已经失败了。如果外层循环正常结束说明第一个字符串本身就是所有字符串的公共前缀直接返回strs[0]。3.3 横向和纵向的适用场景对比维度横向扫描纵向扫描理解难度符合直觉容易讲下标稍绕需要理解“列”最好情况第二个字符串开头不同时很快结束第一列不同时只比较 N-1 个字符就结束最坏情况所有字符串相同O(S)所有字符串相同O(S)额外空间O(1)O(1)代码风险容易忘记更新 prefix容易在 charAt 前忘判断长度从大 O 角度看两种解法都是 O(S)但常数项有差异。纵向扫描在随机数据下通常略快因为它按列推进只要某一列不匹配就整体结束不会反复去比较前面已经确定相同的前缀。横向扫描每轮都要从 0 开始重新比较会有重复操作。所以我个人刷题时更愿意写纵向扫描但面试讲解时一般先讲横向因为横向最好理解等对方点头后再补一句“其实纵向扫描更符合这道题的本质”面试官就会觉得你有思考深度。4. 优化思路的真相分治、二分和排序4.1 分治把数组拆成两半分别求公共前缀再合并分治的思路是定义divide(l, r)返回字符串数组l到r范围内的最长公共前缀。每次取中点mid先递归求左半部分left再求右半部分right最后返回left和right的公共前缀。代码如下class Solution { public String longestCommonPrefix(String[] strs) { if (strs null || strs.length 0) return ; return divide(strs, 0, strs.length - 1); } private String divide(String[] strs, int l, int r) { if (l r) return strs[l]; int mid l (r - l) / 2; String left divide(strs, l, mid); String right divide(strs, mid 1, r); return commonPrefix(left, right); } 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); } }时间复杂度依然可以看作用例中所有字符的总数 S因为每个字符最多参与常数次比较整体 O(S)。但因为递归调用额外空间是递归栈深度 O(log n)。这种解法在本题并不必要面试中主动提出来主要价值在于展示你对分治思想的理解一个大规模问题可以拆成两个规模更小的子问题再合并答案。4.2 二分对最短字符串的长度做二分公共前缀的长度一定不会超过数组中最短字符串的长度。假设最短长度为minLen那么答案长度必然落在[0, minLen]区间。这个区间是单调的如果长度为k的前缀是公共前缀那么所有小于k的长度也一定是如果长度为k不是那么大于k也不可能。所以可以对长度做二分。判断函数如下private boolean isCommonPrefix(String[] strs, int len) { String prefix strs[0].substring(0, len); for (int i 1; i strs.length; i) { if (!strs[i].startsWith(prefix)) { return false; } } return true; }有了这个函数二分主体就很简单了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].substring(0, low);每次判断需要遍历所有字符串复杂度 O(n * mid)二分总共需要 O(log minLen) 次判断所以总复杂度约 O(n * minLen * log minLen)其实比直接横向扫描更差。真正有用的地方在于“二分答案”这个思想如果一个问题的答案是单调整数就能用二分不断逼近。很多复杂题的判断函数很贵但二分可以减少调用次数。4.3 排序排序后只比较首尾两个字符串这个思路很巧妙把字符串数组按字典序排序后整个数组的公共前缀等于排序后第一个字符串和最后一个字符串的公共前缀。为什么成立字典序排序后任意中间字符串都排在首尾字符串之间。如果第一个和最后一个字符串前k个字符完全相同那么中间的字符串为了保证字典序落在其中前k个字符也必须相同如果首尾在第k个字符处不同那么整个有序序列在该位置上的字符就存在一个过渡区间不可能所有字符串都等于同一个字符。代码可以写成Arrays.sort(strs); String head strs[0]; String tail strs[strs.length - 1]; int i 0; while (i head.length() i tail.length() head.charAt(i) tail.charAt(i)) { i; } return head.substring(0, i);排序法的时间复杂度主要取决于排序本身O(n log n * m)其中 m 是字符串平均长度。如果数组很大排序成本不低。但它有一个额外优点排序后代码非常短面试时遇到“不给约束条件”的题目可以作为一种快速方案抛出来。注意Arrays.sort会修改原数组如果题目不允许修改输入需要先clone一份。4.4 这些优化到底值不值得用方法时间复杂度空间复杂度推荐度横向扫描O(S)O(1)最常用纵向扫描O(S)O(1)最推荐分治O(S)O(log n)展示思维二分O(n * minLen * log minLen)O(1)一般不优于前两者排序O(n log n * m)O(1) 或 O(n)特殊场景可用坦率地说这道题本身的最优解就是横向或纵向扫描。分治、二分、排序更多是面试中的“加分动作”用来展示你知道问题可以从不同角度拆解。真正值得投入的优化方向是如果字符串数量很大可以考虑字典树把所有字符串插入字典树然后从根节点向下走只要当前节点只有一个孩子且不是字符串终点就继续走一旦出现分支或结束标记当前路径就是最长公共前缀。这样构建也是 O(S)但空间占用更高。5. 现场写代码的易错点与实用技巧5.1 三个最容易翻车的边界第一个是空数组和空字符串。不判断空数组直接访问strs[0]会抛出异常数组里有空字符串时公共前缀只能是空串应该提前返回。我习惯在循环入口统一处理如果strs null || strs.length 0直接返回在循环中遇到strs[i].isEmpty()也直接返回。第二个是越界。纵向扫描的charAt前必须判断i strs[j].length()横向扫描的while条件里必须同时保证j prefix.length()和j strs[i].length()两个条件少一个都可能出现越界。第三个是substring含头不含尾。返回substring(0, i)时结果不包括索引i也就是已经确认匹配的前i个字符。很多人在这里多写一个i 1结果返回了错误前缀这种问题很难一眼看出来。5.2 复杂度口径怎么讲才能让面试官点头不要张口就背O(n*m)这种公式。更好的说法是“假设所有字符串的字符总数是 S横向扫描每个字符在最坏情况下最多被比较常数次所以整体 O(S)额外空间 O(1)。”面试官听了会觉得你考虑到了输入分布。如果继续问纵向扫描就说“按列扫描在遇到不同字符时立刻退出常数更小尤其适合公共前缀比较短的场景。”5.3 从这道题延伸出去的算法视角把题目稍作变形能带出几个常见的知识模块如果求“最长公共后缀”把每个字符串反转后转成求公共前缀或者从末尾开始按列扫描。如果做“多个字符串的同时匹配”字典树是最自然的工具。如果用startsWith、indexOf等 API能提高编码速度但要理解底层扫描逻辑否则面试官追问底层实现时容易卡壳。二分答案、分治合并、排序后取首尾都是可复用的思维很多字符串和数组题都会用到其中某个思路。5.4 我的个人建议我平时刷题时更习惯写纵向扫描因为它代码短边界处理也更集中但面试我会先讲横向再自然过渡到纵向把“从两两求交集”到“按列对齐”的转换讲清楚。如果面试官追问“还有没有更快的思路”再提排序法和字典树顺便说一下复杂度对比。一道看似简单的 JavaScript 五分钟题这几个层次展开就能聊二十分钟关键不是记住答案而是理解每一种方法在什么数据下表现更好边界条件怎么处理复杂度如何推导。这套分析能力才是刷题真正要练的东西。