最长公共前缀

怎样从“字符串数组 ["flower","flow","flight"],求最长公共前缀。”推导出 字符串基础 · 纵向扫描，并证明每次状态变化都不会漏掉答案？

中心结论：纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

在本站主例中，字符串数组 ["flower","flow","flight"],求最长公共前缀。

算法最终需要得到或观察：公共前缀 "fl"。

每次失配都换起点并从 needle[0] 开始，会丢掉已经确认的前缀；LPS 保存可复用的最长相等真前后缀。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“模式串自救地图”，明确答案需要观察什么。
2. 2状态只维护 列索引 i、行 j、基准字符 ch、已确认前缀 prefix。
3. 3转移每一步按照 纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。
4. 4收尾读取 公共前缀 "fl"。，并复核边界与复杂度。

失配不是清零，而是把模式串移动到下一个仍可能成功的位置。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：列索引 i、行 j、基准字符 ch、已确认前缀 prefix。

对 strs 按照字符串长度进行升序排序，求出 strs 中长度最小字符串的长度 minLen 逐个比较长度最小字符串与其它字符串中的字符，如果不相等就返回 commonPrefix,否则就把该字符加入 commonPrefix

纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。

执行过程中持续维护：列索引 i、行 j、基准字符 ch、已确认前缀 prefix。

正确性依赖以下不变量：在检查第 i 列之前,strs[0][0:i] 已确认是所有字符串的公共前缀。；最短字符串长度是公共前缀的天然上界。

面试时可以压缩为：纵向扫描:固定列 i,基准字符 ch=strs[0][i],逐行比对;任一行提前结束或字符不等立刻返回 strs[0][:i]。时间 O(S) (S 为实际比较字符数),最坏 O(n·m),空间 O(1)。

落到当前题，执行机制可以压缩为：纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入字符串数组 ["flower","flow","flight"],求最长公共前缀。 因为：纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。
2. 2横向扫描,逐步缩短前缀初始候选为第一个串。 因为：LCP 必为第一个串的前缀。
3. 3'flow' 不匹配,前缀缩短为 'flow'缩短直到匹配或空。 因为：不匹配说明当前前缀过长。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5'flight' 不匹配,前缀缩短为 'flo'缩短直到匹配或空。 因为：不匹配说明当前前缀过长。
6. 6'flight' 不匹配,前缀缩短为 'fl'缩短直到匹配或空。 因为：不匹配说明当前前缀过长。
7. 7最长公共前缀 'fl'返回最终前缀。 因为：横向扫描经典法。
8. 8收尾与复杂度公共前缀 "fl"。 因为：时间 O(S) · 空间 O(1)。纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func longestCommonPrefix(strs []string) string {
	prefix := strs[0]

	for i := 1; i < len(strs); i++ {
		for j := 0; j < len(prefix); j++ {
			if len(strs[i]) <= j || strs[i][j] != prefix[j] {
				prefix = prefix[0:j]
				break
			}
		}
	}

	return prefix
}

func main() {
    // 1. 主例
    //    输入：mode="longest-common-prefix", strs=["flower","flow","flight"]
    //    期望：公共前缀 "fl"。
    //
    // 2. 失败 / 未命中
    //    检查：公共前缀不是共同出现的字符,而是从第 0 位开始连续相同的字符。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC58 最后一个单词的长度；LC459 重复子串模式
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意字符串数组 ["flower","flow","flight"],求最长公共前缀。
2. 2重复每次失配都换起点并从 needle[0] 开始，会丢掉已经确认的前缀；LPS 保存可复用的最长相等真前后缀。
3. 3优化纵向比较:固定列 i,逐行比对 s[j][i];任一行字符不同或提前结束即截断前缀。
4. 4证明在检查第 i 列之前,strs[0][0:i] 已确认是所有字符串的公共前缀。；最短字符串长度是公共前缀的天然上界。
5. 5复杂度时间 O(S)，空间 O(1)