最长公共前缀:从左到右验身份

字符串基础 · 纵向扫描

一列一列检查所有字符串,只要某一列不一致,公共前缀立刻结束。这不是子串问题、不是 KMP——只是按列对齐字符。

当前输入 · strs

strs[0]flower

strs[1]flow

strs[2]flight

最终公共前缀

"fl"

fl 后第三列分歧

时间 O(S) · S = 实际比较字符数最坏 O(n · m)空间 O(1) · 只用列/行索引分类:字符串基础

公共前缀不是共同出现过的字符,而是从第 0 位开始连续相同的字符。

只要某一列出现不同,后面再像也没有意义,因为前缀已经断了。

最短字符串的长度是公共前缀的天然上限。

纵向扫描的本质是按列确认答案,每通过一列,答案长度加一。

初始化Step 1 / 13

前缀安检闸机 · 第 0 列

base ch = — · row j = —

strs[0]

基准

strs[1]

∅

strs[2]

答案槽 · prefix

长度 0 / 最终 2

(尚未确认任何字符)

状态:待启动输入 3 个字符串,准备从第 0 列开始纵向扫描。

代码同步 · Go

初始化

1func longestCommonPrefix(strs []string) string {
2    if len(strs) == 0 {
3        return ""
4    }
5 
6    for i := 0; i < len(strs[0]); i++ {
7        ch := strs[0][i]
8 
9        for j := 1; j < len(strs); j++ {
10            if i == len(strs[j]) || strs[j][i] != ch {
11                return strs[0][:i]
12            }
13        }
14    }
15 
16    return strs[0]
17}

机器状态

动作: 初始化
列索引 i: 0
行索引 j: —
基准字符 ch: —
本格字符: —
当前 prefix: ""
目标答案: "fl"

为什么可以继续

最长公共前缀必然是 strs[0] 的某个前缀,所以以 strs[0] 为基准、一列一列检查所有其他字符串就够了。

面试表达 · 纵向扫描:以 strs[0] 为基准,逐列对齐所有字符串,首次出现不一致就截断。

循环不变量

尚未确认任何字符,prefix = ""。

步骤时间线

面试 · 一段话讲清

以 strs[0] 为基准做纵向扫描。固定列 i,取基准字符 ch = strs[0][i]; 逐行检查 strs[j][i]:任一行已经提前结束 (i == len(strs[j])) 或字符不等,立即 return strs[0][:i]。整列通过则 prefix 长度 +1,继续下一列。时间 O(S),S 为实际比较的字符总数,最坏 O(n · m),空间 O(1)。

常见误区

✗ 把"共同出现过的字符"误当成公共前缀——前缀必须从第 0 位开始连续相同。
✗ 内层循环忘了判断 i == len(strs[j]) 就直接取 strs[j][i],会在短串/空串上越界。
✗ 把这题归类为 KMP 或后缀数组——它只是纯按列对齐,不需要任何子串匹配。
✗ 一次次截短第一个字符串再比 (横向扫描) 也对,但容易写成 O(n · m²), 纵向扫描在首列就能尽早退出,更稳。