#14
简单
低频
迭代法最长公共前缀
这是一道围绕数组、字符串展开的高频练习。建议先掌握「迭代法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
字符串
题目分析
这道题表面上是在处理「最长公共前缀」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 数组、字符串 这些能力。这类题通常不难想到总体方向，真正容易乱的是遍历顺序、边界收缩和状态更新的先后关系。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：先把第一个字符串当作前缀候选，再依次和后面的字符串做前缀收缩。
推荐代码
推荐解法：迭代法
时间复杂度： O(S)
空间复杂度： O(1)
核心思路： 先把第一个字符串当作前缀候选，再依次和后面的字符串做前缀收缩。
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length <= 0) {
return "";
}
String ans = strs[0];
for (int i = 1; i < strs.length; i++) {
int j = 0;
while (j < strs[i].length() && j < ans.length()) {
if (strs[i].charAt(j) != ans.charAt(j)) {
break;
}
j++;
}
if (j < ans.length()) {
ans = strs[i].substring(0, j);
if (ans.equals("")) {
return ans;
}
}
}
return ans;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用前缀收缩法，逐步缩小当前公共前缀。
核心过程
- 先把第一个字符串作为候选前缀。
- 遍历后续每个字符串。
- 如果当前字符串不以候选前缀开头，就不断缩短候选前缀。
- 遍历结束后剩下的前缀就是答案。
复杂度总结
时间复杂度与所有字符总数同阶，空间复杂度 O(1)。
面试补一句：这题的核心直觉是：公共前缀只会收缩，不会扩张。
核心思路
最长公共前缀不需要两两全比，只要维护当前公共前缀，遇到新字符串时把它缩短到仍然匹配为止即可。
步骤讲解
1
先把第一个字符串当候选前缀
初始化答案为数组第一个字符串。
为什么这样做：最终公共前缀一定不会比它更长。
对应代码提示：String prefix = strs[0];
2
依次与后续字符串收缩匹配
如果当前字符串不以 prefix 开头，就不断缩短 prefix。
为什么这样做：公共前缀只能越来越短，不会变长。
对应代码提示：while (!strs[i].startsWith(prefix)) prefix = prefix.substring(0, prefix.length() - 1);
3
前缀缩成空串就可提前结束
若 prefix 变为空，说明不存在公共前缀。
为什么这样做：空串已经是最短可能答案。
对应代码提示：if (prefix.isEmpty()) return "";
易错点
直接逐列比较却不处理短串
容易访问越界。
正确理解：要么显式判断长度，要么用前缀收缩法避免越界。
把公共子串和公共前缀混淆
题目要求必须从开头连续匹配。
正确理解：所有判断都围绕字符串开头。
前缀收缩时没及时停止
会继续做无意义比较。
正确理解：一旦前缀变空即可返回。
复杂度与适用判断
时间复杂度：O(S)
空间复杂度：O(1)
比其他方案更好在哪里：比排序后比首尾也更直观，易于面试现场推导。
适用判断：字符串数组题若答案只会越来越短，优先考虑“维护候选并不断收缩”。
额外提醒
- 公共前缀的长度是单调递减的。
动画演示
如果你还没完全看懂，可以展开动画演示。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入字符串列表（用逗号分隔），然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。