LeetCode 14. 最长公共前缀
题目描述
题意分析
给定一组字符串，找出它们共同拥有的最长开头部分。前缀必须从每个字符串的下标
0开始，并连续延伸，不能跳过字符，也不能从字符串中间开始寻找。只要某个位置有字符串结束，或同一位置出现不同字符，公共前缀就不能继续扩展。没有共同的开头时返回空字符串；数组至少包含一个字符串，但其中的字符串可以为空。
解法：纵向逐列比较字符
核心思路
[!blue]
公共前缀一定是第一个字符串的某个前缀，因此可以用它作基准，逐个位置向右尝试扩展，不需要先排序或建立额外的数据结构。
假设已经确认所有字符串的区间
[0, idx)完全相同。要再加入第idx个字符，就必须让每个字符串都存在这个位置，并且该字符都与基准串一致；逐个比较其他字符串即可验证这一条件。如果发现某个字符串已结束，公共前缀不可能比它更长；如果发现字符不同，任何更长前缀都会包含这一处差异。两种情况都能立即停止，而此前已经确认的
[0, idx)正好是最长答案，失配位置本身不应包含在返回值中。如果把基准串完整扫描完仍然一致，它的全部字符都属于公共前缀。又因为任何公共前缀都不可能超过基准串本身，所以直接返回它就是最优结果。基准为空时循环不执行，自然返回空字符串；只有一个字符串时，它本身就是答案。
解题步骤
- 取
strs[0]为基准串first，从下标idx = 0开始扫描。- 对当前位置，依次检查其他字符串：先判断它是否已经结束，再比较字符是否与
first[idx]相同。- 只要有一串结束或失配，立即返回基准串的左闭右开区间
[0, idx)。- 当前列全部匹配后再检查下一列；若基准串全部扫描完成，返回整个
first。
代码实现
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)$，不计返回字符串，只使用常数个变量。
关键点总结
[!green]
- 答案一定包含在任意一个输入字符串中，选第一串作为基准就足够。
- 每次确认一整列，可以保证左边已经匹配的部分始终是所有字符串的公共前缀。
- 第一处不匹配决定答案终点，后面的字符即使再次相同，也不能越过这处差异继续扩展。
易错点总结
[!yellow]
- 先读取字符再检查长度，会在遇到较短字符串时越界；代码依靠
||短路，先判断是否已经结束。- 返回区间包含失配位置，会多取一个不属于公共前缀的字符，终点应保持为不包含
idx。- 忽略空字符串，会错误地继续比较其他字符串；任意一串为空，公共前缀就只能为空。
- 失配后继续寻找后面的相同字符，求出的就不再是连续的公共前缀。
- 本题字符限定为小写英文字母，Go 按字节索引与按字符比较一致。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | Trie把相同前缀合并为公共路径，本题只需找到全部字符串共享路径的终点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！