14. 最长公共前缀（Longest Common Prefix）

频次 ★★★ · 难度 🟢 · 高频：字节/腾讯

题目

编写一个函数返回字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例：

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""

思路

横向扫描：先取第一个字符串作为公共前缀，然后依次与后面的每个字符串比对，每轮缩短公共前缀，直到匹配或为空。

也可以用纵向扫描：同时比较所有字符串的第 i 个字符，如果全部相同则加入结果，否则停止。纵向扫描在输入较大时可能提前退出，但两者时间效率接近。

代码

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
 
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

复杂度

• 时间：O(S) — S 为所有字符串的总字符数
• 空间：O(1)

边界条件

• 空数组：直接返回 ""。
• 只有一个字符串：返回该字符串本身。
• 第一个字符串为空串：首轮 prefix 即为 ""，后续循环 indexOf("") == 0 恒成立，最终返回 ""。

变式

• 纵向扫描：固定列索引 i，对每行的第 i 位比较，遇到越界或不相等就返回前 i 位结果。适合短公共前缀或输入非常大的场景，可以提前终止。
• 分治法：将数组分成左右两半，分别求 LCP，再合并（lcp(left, right)）。时间复杂度相同，但代码更复杂。
• Trie 树：将所有字符串插入 Trie 树，从根节点往下走，直到遇到分支或结束标记。适合多批次查询相同的字符串集合。

易错点

• indexOf(prefix) != 0 判断的是前缀是否匹配开头，不是 contains 或 startsWith（Java 中可用 startsWith 代替，更直观）。
• substring 每次生成新字符串，频繁截断在字符串很长时会有 O(L²) 的性能损耗（但本题字符串长度通常不大）。
• 不要忘记 strs == null 的判空。

面试追问

• 如果只给两个很长的字符串，求最长公共前缀怎么办？ 直接用 while + indexOf 截断法效率足够；也可以转换为”两字符串逐位比较”（纵向），不需要额外空间。
• Trie 树方案有什么优缺点？ 优点是建树后任意新字符串求 LCP 只需 O(L) 匹配；缺点是建树本身 O(S) 时间和 O(S) 空间，且只适合多查询场景。

关联题

• 同套路：分治法 LCP 是归并思想在字符串上的应用
• 进阶：208. 实现 Trie —— 前缀匹配的经典数据结构
• 基础：字符串匹配基本功见数组与字符串