最长公共前缀 图解题解
把所有词竖着摞、逐列扫，一有不同立刻停，O(S) 拿到最长公共前缀。
把所有单词竖着摞成一列，逐列往右看：只要这一列每个词的同位字母和第一个词的一样，就算进公共前缀；一旦有词短了、或某个字母对不上，立刻停——摞着比比列，比两两再取交集清爽得多。
这道题到底在问什么
- strs
- ["flower", "flow", "flight"]
- 输出
- "fl"
最优解：一步一步想明白
- 3朴素想法：把字符串两两比公共开头、再取交集，反复比较还纠结拿哪个词当基准。有更清爽的办法：直接竖着对齐、一列一列检查。
- 4为什么成立：公共前缀必然是每一列上所有词都相同的那段连续字符。拿第 0 个词当基准，逐列检查其余词的同位字符是否都和基准一样；只要有一个不同、或某个词已到头，就立刻停，前面对齐的部分就是答案。
- 5基准 flower，cur=0，待查第 0 列把三个词竖着摞起来。台上这行是基准词 "flower"，列指针 cur 指向第 0 列，准备看 flow、flight 在这一列是不是也和基准一样。
- 6cur=0 flower/flow/flight 这一列都是 f第 0 列：flow 首字母是 f、flight 也是 f，和基准 flower 的 f 一样。这一列纳入公共前缀，cur 前移。
- 7cur=1 这一列都是 l第 1 列：三个词都是 l，仍然一致。公共前缀长到 "fl"，cur 继续前移到第 2 列。
- 8cur=2 基准 flower[2]=o前两列都对齐，cur 前移到第 2 列。基准 flower 这一位是 o，接下来逐个看其余词在这一列是不是也都是 o。
- 9cur=2 flow[2]=o，和基准一样先看 flow，flow[2] 也是 o，和基准对得上，暂时没分歧。继续看下一个词 flight。
- 10cur=2 flight[2]=i ≠ 基准 o转折：再看 flight，flight[2] 是 i，和基准的 o 不相等！这一列出现分歧——立刻停下，第 2 列往后全部作废。这就是 "一列不齐即止"。
- 11在第 2 列断开，answer="fl"在第 2 列断开，截取基准词已对齐的前 2 位："fl"，就是最长公共前缀。
- 14公共前缀的直觉：把多个词竖着摞起来一列一列对齐，第一处不齐就是边界。这种纵向对齐思路在很多多字符串问题里都能复用。
- 16cur=1 基准 ab[1]=b，但 "a" 没有第 1 列真跑一个会踩坑的小例子：基准 "ab"，另一个词是 "a"。第 0 列都是 a ✓；到第 1 列基准是 b，但 "a" 已经没有第 1 个字母了——i 等于它的长度，越界条件触发，立刻停，返回 "a"。这就是 "前缀不能超过最短的词"。
- 20练会这题后，去字符串专题里迁移：所有 "多个串比共同部分" 的题，都复用 "拿一个串当基准、逐位核对、第一处不齐即止" 这套思路。卡住可以问 AI 助教 小欧，或去通关训练里再刷两道。
⚠️ 容易写错的地方
✗ 错：只比字符、不判某词是否到头
✓ 对：把 i 等于该词长度 一起当停止条件
前缀不能超过最短的词；漏判会用 s[i] 越界访问、直接崩溃
✗ 错：空数组没特判就直接取 strs[0]
✓ 对：开头先判 strs 为空就返回空串
空数组时 strs[0] 会下标越界
✗ 错：以为含空串要专门写特判
✓ 对：靠 i 等于 len(s) 条件自然截断即可
空串长度为 0，第 0 列就触发越界条件返回空串，不必额外加判断
完整代码（Python / C++ / Java）
Python
class Solution:
def longestCommonPrefix(self, strs):
if not strs:
return ''
for i in range(len(strs[0])):
ch = strs[0][i]
for s in strs[1:]:
if i == len(s) or s[i] != ch:
return strs[0][:i]
return strs[0]C++
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int i = 0; i < (int)strs[0].size(); i++) {
char ch = strs[0][i];
for (int k = 1; k < (int)strs.size(); k++) {
if (i == (int)strs[k].size() || strs[k][i] != ch)
return strs[0].substr(0, i);
}
}
return strs[0];
}
};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 ch = strs[0].charAt(i);
for (int k = 1; k < strs.length; k++) {
if (i == strs[k].length() || strs[k].charAt(i) != ch)
return strs[0].substring(0, i);
}
}
return strs[0];
}
}套路模板 · 纵向扫描骨架（可默写）
if not strs: return '' # 空数组特判
for i in range(len(strs[0])): # 以首词逐列
ch = strs[0][i] # 基准字符
for s in strs[1:]: # 其余词比该列
if ____ or ____: # ① 越界？ ② 字符不同？
return strs[0][:i] # 第一处不齐即截断
return strs[0] # 全部通过，返回基准词if (strs.empty()) return "";
for (int i = 0; i < (int)strs[0].size(); i++) {
char ch = strs[0][i];
for (int k = 1; k < (int)strs.size(); k++) {
if (/* ①越界 */ || /* ②字符不同 */)
return strs[0].substr(0, i);
}
}
return strs[0];if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
char ch = strs[0].charAt(i);
for (int k = 1; k < strs.length; k++) {
if (/* ①越界 */ || /* ②字符不同 */)
return strs[0].substring(0, i);
}
}
return strs[0];复杂度
时间复杂度
O(S)
S = 所有字符串字符总数；最坏全部相同要扫完，通常很早就在某列断开
空间复杂度
O(1)
只用列指针与字符变量，不开额外结构（返回值不计）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长公共前缀 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
纵向、横向、分治、二分四种写法，时间复杂度各是多少？+
四种最坏都是 O(S)（S 为所有字符总数）。纵向/横向常数小且直观；分治递归两两合并 O(S)；二分锁前缀长度时最坏 O(S·logm)（m 为最短串长）但代码复杂。面试首选纵向扫描，好写不易错。
遇到比 cur 短的串要停，为什么不能只判字符是否相等？+
若某串比 cur 短，直接访问 s[cur] 会越界崩溃。必须把 "i 等于该串长度" 和 "字符不同" 并列为停止条件，任一成立就截断——这也对应了 "前缀不能超过最短的串"。
如果字符串数量极多、但都很短，哪种写法更省？+
纵向扫描天然友好：只要某一列出现分歧就立刻整体停止，无需把每个串都完整读完。横向法则要拿前缀和每个串逐一比对、命中最坏才停，常数更大。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。