AlgoViz Lab交互式算法学习Algorithms first
最长公共前缀 · 交互式算法学习
找出所有字符串的最长公共前缀。
#14 · 数组 / 字符串
最长公共前缀
Longest Common Prefix
strs = ["flower","flow","flight"]线性序列3 个关键状态
步骤 1候选前缀先取 flower。
prefix=flowerflower
0flow
1flight
2推荐
不断缩短候选前缀
时间
O(S)空间 O(1)先把第一个字符串当候选；每遇到不匹配就从尾部缩短。
1function longestCommonPrefix(strs) {2 let prefix = strs[0];3 for (const s of strs.slice(1))4 while (!s.startsWith(prefix)) prefix = prefix.slice(0, -1);5 return prefix;6}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public String longestCommonPrefix(String[] strs) {3 int n = strs.length;4 for (int i = 0; i < strs[0].length(); ++i) {5 for (int j = 1; j < n; ++j) {6 if (strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) {7 return strs[0].substring(0, i);8 }9 }10 }11 return strs[0];12 }13}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
最长公共前缀 · 解法对比
找出所有字符串的最长公共前缀。
- 测试用例
strs = ["flower","flow","flight"]- 题目分类
- 数组 / 字符串
- 解法对比
- 2
纵向逐列比较
同一列字符全部相同就继续，否则在该列前结束。
- 时间
O(S)- 空间
O(1)
不断缩短候选前缀
先把第一个字符串当候选；每遇到不匹配就从尾部缩短。
- 时间
O(S)- 空间
O(1)
为什么有效
同一列字符全部相同就继续，否则在该列前结束。
关键不变量
每一步都保持当前方法的已处理部分正确，并朝“找出所有字符串的最长公共前缀。”推进。
易错点
- 先确认输入边界与下标范围。
- 代码、变量状态与动画步骤应保持一致。
边界情况
- 空输入或最小规模输入。
- 重复值、极端顺序或退化结构。
更多案例
strs = ["flower","flow","flight"]找出所有字符串的最长公共前缀。同一列字符全部相同就继续，否则在该列前结束。