LeetCode 14. 最长公共前缀
目录
题目描述
题意分析
给定一个字符串数组，要求返回所有字符串共有的最长开头段。「公共」是关键约束：答案必须同时是数组里每一个字符串的前缀，缺一个都不行；如果不存在公共前缀，返回空字符串
""。一个直接的推论是：答案的长度不会超过数组中最短的字符串，因此答案一定是任意一个字符串（比如第一个）的某个前缀，问题就变成确认这个前缀能延伸到多长。
约束上数组长度和单串长度都不超过 200，规模很小，任何合理做法都能过，考的是边界处理是否干净。
边界情况：数组里含空串时答案必为
""；数组只有一个字符串时答案就是它本身；所有字符串完全相同时答案是整个字符串。
解法：纵向逐列比较字符
核心思路
问题关键：答案一定是任意一个字符串的前缀，并且长度不会超过最短字符串。只要找到从第 0 列开始第一个不一致的位置，就确定了答案边界。
为什么选纵向扫描：把字符串上下对齐，逐列检查所有字符串。某列出现字符不同，或某个字符串已经结束，就可以立即返回；不需要额外排序、字典树或反复截取候选前缀。
不变量：进入第
idx列时，所有字符串的[0, idx)已经完全相同。若当前列验证失败，最长公共前缀恰好是first[0:idx]；若基准串全部验证完，它本身就是答案。这个不变量同时说明了算法不会漏掉更长前缀，也不会返回包含失配字符的结果。
解题步骤
- 取第一个字符串
first作为基准，按下标从左到右扫描。- 对每个下标
idx，检查其余字符串是否仍有该位置，且字符是否等于first[idx]。- 任一字符串越界或字符不同，立即返回
first[0:idx]。- 如果基准串全部扫描完，说明它的所有字符都属于公共前缀，直接返回
first。例如
["flower","flow","flight"]的第 0、1 列都相同，第 2 列o != i，因此返回[0,2)，即"fl"。
代码实现
class Solution {
public String longestCommonPrefix(String[] strs) {
String first = strs[0];
for (int idx = 0; idx < first.length(); idx++) {
char ch = first.charAt(idx);
for (int i = 1; i < strs.length; i++) {
// 当前列只要有一个字符串缺失或不同，前缀就在这里结束。
if (idx == strs[i].length() || strs[i].charAt(idx) != ch) {
return first.substring(0, idx);
}
}
}
return first;
}
}
func longestCommonPrefix(strs []string) string {
first := strs[0]
for idx := 0; idx < len(first); idx++ {
ch := first[idx]
for i := 1; i < len(strs); i++ {
// 同一列出现越界或字符不同，立即返回已确认前缀。
if idx == len(strs[i]) || strs[i][idx] != ch {
return first[:idx]
}
}
}
return first
}
复杂度分析
- 时间复杂度：$O(S)$，
S为所有字符串的字符总数；遇到失配会提前结束。- 空间复杂度：$O(1)$，不计返回字符串，只使用常数个变量。
关键点总结
- 公共前缀等价于「从左开始连续相同的列」。
- 必须先判断字符串长度，再访问当前位置，依赖短路避免越界。
- 失配位置不属于答案，所以返回的是左闭右开区间
[0, idx)。- 字典树适合大量字符串的重复前缀查询；本题只求一次，纵向扫描更直接。
易错点总结
- 先取字符再判断长度会越界：
["ab","a"]扫到下标 1 时会抛异常。- 失配时不能包含当前列；
["flower","flow","flight"]应返回"fl"，不是"flo"。- 遇到空串必须立刻得到
""，长度判断不能省略。- 单元素数组的答案就是该字符串本身，不需要额外特判。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 把前缀关系固化成字典树，支持反复插入与查询 |
| 1143. 最长公共子序列 | 中等 | 匹配从连续开头段放宽为子序列，需要动态规划 |