如何求一组字符串的最长公共前缀？（LeetCode 14）

简化版

给一组字符串，求它们的最长公共前缀（都相同的开头那段），没有则返回空串。最直观的纵向扫描：以第一个字符串为基准，逐列（第 0 个字符、第 1 个字符……）比较所有字符串的同一位置，一旦发现某个字符串在这一列不同（或已到末尾），前面扫过的部分就是答案。也可用横向扫描（两两求公共前缀逐步缩小）或分治/二分。

详细版

纵向扫描（推荐，直观）

String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int col = 0; col < strs[0].length(); col++) {  // 逐列
        char c = strs[0].charAt(col);
        for (int i = 1; i < strs.length; i++) {         // 比较每个字符串的这一列
            if (col == strs[i].length() || strs[i].charAt(col) != c) {
                return strs[0].substring(0, col);       // 到此为止即公共前缀
            }
        }
    }
    return strs[0];   // 第一个串本身就是公共前缀（它最短或都相同）
}

横向扫描（两两缩小）

String longestCommonPrefix(String[] strs) {
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {          // prefix 不是 strs[i] 的开头
            prefix = prefix.substring(0, prefix.length() - 1);  // 缩短一位
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

纵向扫描：一列一列比，遇到不一致就停，直观且最坏 O(总字符数)。
横向扫描：用第一个串当初始前缀，和后面每个串求公共前缀不断缩短。
复杂度：都约 O(S)，S 是所有字符总数。

完整版教学

一、题意与思路总览

「最长公共前缀」就是所有字符串从头开始都相同的那一段。关键性质：公共前缀的长度不会超过最短的字符串，且只要有一个字符串在某位置不同，公共前缀就到此为止。围绕这个性质有几种扫描方式，核心都是「逐字符比较、遇到不同即停」。

二、纵向扫描：一列一列比

把这组字符串想象成对齐排列的表格，纵向扫描就是一列一列往下比：

取第一个字符串的第 col 个字符 c 作基准。
检查其余每个字符串的第 col 个字符是否也是 c——或者某个字符串长度不够（col == 长度，说明它已经结束）。
一旦发现不一致或越界，strs[0].substring(0, col)（前 col 个字符）就是最长公共前缀。
若所有列都比完没中断，说明第一个字符串整体就是公共前缀。

纵向扫描直观、最坏情况 O(所有字符总数)——但实际上遇到第一个差异列就提前退出，通常很快。

三、横向扫描：两两求公共前缀

另一种思路：先拿第一个字符串当作「当前公共前缀」，再依次和后面每个字符串比较，不断把公共前缀缩短，直到它成为当前字符串的前缀为止。全部比完，剩下的 prefix 就是答案。像 LCP(s1, s2, s3) = LCP(LCP(s1, s2), s3)，逐个归并。若中途 prefix 缩成空串，直接返回空（无公共前缀）。

四、分治与二分（进阶）

分治：LCP(所有串) = LCP(LCP(左半), LCP(右半))，递归二分数组，合并时求两个前缀的公共部分。O(S)，思路优雅但常数略大。
二分答案：公共前缀长度在 [0, 最短串长] 之间，二分这个长度 L，检查是否所有串的前 L 个字符都相同。O(S log m)。属加分解法，面试用纵向扫描足矣。

五、边界与陷阱

空数组 / null：直接返回 ""。
某个字符串是空串：公共前缀必为空（空串没有任何前缀可匹配）。纵向扫描里 col == strs[i].length() 在 col=0 时就触发，返回 ""，正确。
只有一个字符串：公共前缀就是它自己。
易错：越界。比较第 col 位前要判断每个字符串是否够长（col < 长度），否则 charAt(col) 抛异常。纵向扫描的 col == strs[i].length() 判断就是防这个。

六、公共前缀长度具有单调性

无论纵向还是横向扫描，候选前缀只会缩短，不会重新增长。纵向扫描第 i 列前，已经证明所有字符串的 [0,i) 相同；一旦某字符串长度等于 i 或字符不同，任何更长前缀都不可能成立，可以立即返回。

输入 ["flower", "flow", "flight"]
第 0 列都是 f -> 前缀 "f"
第 1 列都是 l -> 前缀 "fl"
第 2 列为 o,o,i -> 首次失配
返回 "fl"
若输入含空串，扫描第 0 列前就触及长度边界
答案为空串

校验维度	本题必须保持的结论
循环/递推不变量	扫描第 i 列时，所有字符串的前 i 个字符已经确认相同。
边界条件	空数组按接口约定通常返回空串；任一字符串为空时答案必为空。
复杂度与代价	最坏比较所有字符串的公共扫描长度，总字符比较 O(S)，S 为输入字符总数上界。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：扫描第 i 列时，所有字符串的前 i 个字符已经确认相同。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“输入 [“flower”, “flow”, “flight”]”开始手推，最后应得到“答案为空串”。
边界复核：空数组按接口约定通常返回空串；任一字符串为空时答案必为空。
代价复核：最坏比较所有字符串的公共扫描长度，总字符比较 O(S)，S 为输入字符总数上界。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“扫描第 i 列时，所有字符串的前 i 个字符已经确认相同。”这条正确性主线不能省。

八、常见误区与追问

误区：公共前缀可以从字符串中间开始。 前缀必须从下标 0 开始，中间公共片段属于公共子串问题。
误区：只比较第一条和最后一条原始输入即可。 只有先按字典序排序后，比较排序后的首尾才足以约束全部字符串。
误区：时间复杂度固定是 O(nm)。 更准确取决于实际比较字符数，遇到早期失配会提前结束。
追问：横向扫描为何正确？ 多个字符串的公共前缀等于逐步取当前前缀与下一个字符串的公共前缀。
追问：二分前缀长度依据什么？ “长度 L 是公共前缀”对 L 具有前真后假的单调性，可二分最大可行 L。
追问：大量字符串在线加入时如何维护？ 维护当前公共前缀，新字符串到来时与其收缩；前缀一旦为空可直接停止。

九、加强记忆

最长公共前缀 = 逐字符比较、遇到不同即停。纵向扫描（推荐）：以第一个串为基准一列一列比，某串在这列字符不同或已到末尾，就返回前面扫过的部分 substring(0, col)。横向扫描：拿第一个串当前缀，和后面每个串比、不断缩短到成为其前缀。都约 O(总字符数)。进阶有分治、二分答案。牢记边界：空串/空数组返回 ""、比较前判越界、公共前缀不超过最短串。核心：竖着扫，撞到第一个不一样就收工。

简化版

详细版