最长公共前缀

题目描述

给定一个字符串列表 words，求所有字符串的最长公共前缀，并返回该字符串。前缀必须从每个字符串的第一个字符开始，且字符顺序连续；不存在非空公共前缀时返回空字符串 ""。

使用分治法求解，不修改输入列表。列表可以为空，也可以包含空字符串、重复字符串或单个字符串。空列表约定返回 ""，单个字符串的答案就是它自身。比较区分大小写，按 Python 字符串中的字符位置进行，不进行大小写转换。

设字符串个数为 $n$，各字符串长度可以不同，最长字符串长度记为 $\ell$。列表下标和字符下标均从0开始。

示例：

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

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

输入： ["", "abc"]
输出： ""

公共前缀不是公共子串，也不是公共子序列。例如 "abc" 与 "xbc" 的公共前缀为空，尽管它们都包含 "bc"。

题目分析

将字符串集合分成左右两组

把字符串列表分成两组，分别求出左组的最长公共前缀 left_prefix 和右组的最长公共前缀 right_prefix。所有字符串共有的前缀，必须同时是这两个结果的前缀。

因此，当前问题的答案就是 left_prefix 与 right_prefix 的最长公共前缀。与同时求最大值与最小值一样，左右子调用各返回一个摘要；这里的摘要是字符串，合并操作是从首字符开始逐个比较。

定义函数、边界与合并规则

内部函数 solve(lo, hi) 返回列表半开区间 [lo, hi) 中所有字符串的最长公共前缀。

• 对外函数先处理空列表，返回 ""。
• 区间只有一个字符串时，直接返回 words[lo]。
• 更长区间按 mid = (lo + hi) // 2 分成 [lo, mid) 和 [mid, hi)，分别求解，再合并两个前缀。

定义 common_prefix(left, right) 求两个字符串的最长公共前缀。从字符下标0开始比较，最多比较到较短字符串的末尾；遇到第一个不同字符就停止，返回已经匹配的部分 left[:index]。

例如 "flower" 与 "flow" 的答案为 "flow"，因为较短者已经全部匹配。"flow" 与 "flight" 比较到下标2时遇到 o 和 i 不同，因此返回 "fl"。

为什么结果正确

单个字符串的最长公共前缀显然是它自身。假设两个子调用正确，那么任意一个左组字符串都以 left_prefix 开头，任意一个右组字符串都以 right_prefix 开头。两者的公共前缀必然也是所有字符串的公共前缀。

反过来，所有字符串的任意公共前缀，也必须同时是左组与右组最长公共前缀的前缀。因此，合并得到的最长结果不会遗漏更长的全局公共前缀。

区间每次变短，最终到达单字符串边界，所以递归能够终止并返回正确答案。

实现代码

Python 递归实现

以下代码可以完整复制到 Python 文件中运行。下标区间避免复制字符串列表；合并时仍会按需要生成前缀字符串。

def common_prefix(left, right):
    """返回两个字符串的最长公共前缀。"""
    limit = min(len(left), len(right))
    index = 0
    while index < limit and left[index] == right[index]:
        index += 1
    return left[:index]


def longest_common_prefix(words):
    """用分治法返回全部字符串的最长公共前缀。"""
    if not words:
        return ""

    def solve(lo, hi):
        if hi - lo == 1:
            return words[lo]

        mid = (lo + hi) // 2
        left_prefix = solve(lo, mid)
        right_prefix = solve(mid, hi)
        return common_prefix(left_prefix, right_prefix)

    return solve(0, len(words))


if __name__ == "__main__":
    cases = [
        ["flower", "flow", "flight"],
        ["dog", "racecar", "car"],
        ["", "abc"],
        ["cat"],
        [],
    ]
    for words in cases:
        print(f"{words} -> {longest_common_prefix(words)!r}")

输出：

['flower', 'flow', 'flight'] -> 'fl'
['dog', 'racecar', 'car'] -> ''
['', 'abc'] -> ''
['cat'] -> 'cat'
[] -> ''

!r 让输出显示字符串的引号，便于辨认空字符串。前缀字符串是每层的局部结果；Python 字符串不可变，代码不修改输入内容。

本实现始终分别处理左右两组，再合并结果；即使左组前缀已经为空，也仍会处理右组。后文的执行过程和复杂度按这一实现分析。

算法执行过程

递归调用：划分字符串列表

以 ["flower", "flow", "flight"] 为例：

solve(0, 3)
├── solve(0, 1) → "flower"
└── solve(1, 3)
    ├── solve(1, 2) → "flow"
    └── solve(2, 3) → "flight"
    合并 "flow" 与 "flight" → "fl"
整体合并 "flower" 与 "fl" → "fl"

划分的是字符串列表的位置区间，不是把每个单词从中间切开。长度3的列表分成长度1和2，符合实际代码。

递归返回：逐字符合并前缀

合并输入	匹配过程	停止原因	返回值
"flow" 与 "flight"	下标0的 f 相同，下标1的 l 相同	下标2的 o 与 i 不同	"fl"
"flower" 与 "fl"	下标0、1均相同	较短字符串已经全部匹配	"fl"

第一次合并进行了3次字符相等比较，第二次进行了2次，共5次。字符比较次数与递归调用次数不同；本例共有5次 solve 调用。

边界：空前缀怎样参与合并

对 ["", "abc"]，两个单字符串子调用分别返回 "" 与 "abc"。合并时 limit = 0，循环不执行，直接返回空字符串。

对 ["cat"]，函数直接返回 "cat"，不进入合并；对空列表，对外函数在进入递归前直接返回 ""。

复杂度分析

设字符串个数为 $n$、最长字符串长度为 $\ell$。按一次字符索引与相等比较为常数时间计费；创建长度为 $p$ 的前缀切片，时间和字符串存储上界按 $O(p)$ 计算。

时间复杂度

对非空列表，调用树有 $n$ 个单字符串叶子和 $n-1$ 个合并节点。一次合并最多比较 $\ell$ 个字符，并生成长度不超过 $\ell$ 的前缀，时间上界为 $O(\ell+1)$，因此总时间上界为：

$$O\bigl(n(\ell+1)\bigr).$$

当 $n\geq2$ 且 $\ell\geq1$ 时，可简写为 $O(n\ell)$；相同的非空长字符串会使每次合并都检查完整前缀，达到这一数量级。若全部字符串为空，仍需处理调用树，时间为 $O(n)$，不能因为字符数为0就认为没有工作量。

空列表直接返回，单个字符串直接返回已有字符串引用，二者均为常数时间。这里没有对输入进行排序。

辅助空间复杂度

递归栈深度为 $O(\log(n+1))$。输入列表没有被切片，但合并结果可能创建新的前缀字符串；处理右子问题时，当前层已经求出的左前缀仍需保留。

对于 $n\geq2$，沿当前调用链可能同时保存对数层的前缀，每个长度不超过 $\ell$，再加上调用栈，辅助空间上界为 $O((\ell+1)\log(n+1))$。这一上界计入中间前缀存储，不能只报告调用栈的空间。最终返回字符串长度不超过 $\ell$；空列表和单字符串边界只使用常数辅助空间。

这一实现用于清楚展示“分组求解，再合并摘要”。其他表示方式可以减少中间字符串分配，但需要重新分析其实现和空间使用。

易错点

易错点	正确理解
将公共子串或子序列当成前缀	前缀必须从每个字符串的下标0开始，且连续
只比较列表中的前两个字符串	要覆盖全部字符串，左右两组结果都参与合并
单字符串边界返回空字符串	单个字符串本身就是这一组的最长公共前缀
使用较长字符串长度控制比较	最多比较到较短者末尾，避免越界
遇到不同字符后继续跳过它比较	第一次不同就应停止，后面相同字符不能补进前缀
空列表直接访问 words[0]	对外函数先处理空列表
默默转为小写再比较	本题区分大小写，转换会改变题意
根据递归深度直接写时间 $O(\log n)$	两侧都递归，且每次合并可能比较多个字符
辅助空间只算递归栈	本实现还可能创建并保留中间前缀字符串

课堂练习

1. 对 ["flower", "flow", "flight", "flute"]，第一层左右两组分别返回什么？最终答案是什么？
2. ["ab", "abc"]、["abc", "xbc"]、["A", "a"]、["", ""] 分别返回什么？
3. 为什么当前代码对 ["flow", "flight"] 会进行3次字符相等比较，而答案只有2个字符？
4. 如果有8个相同的字符串 "abc"，本实现合并几次、进行多少次字符相等比较？
5. 为什么这篇文档的空间分析不能照搬只保存数值的最大最小值算法？

参考答案

1. 左组 ["flower", "flow"] 返回 "flow"，右组 ["flight", "flute"] 返回 "fl"；两者合并，最终返回 "fl"。
2. 分别为 "ab"、""、""、""。较短者完全匹配即可作为答案；公共前缀必须从首字符开始，并区分大小写。
3. 除了比较两个匹配字符，还要比较下标2处的 o 与 i 才发现不相等并停止。
4. 8个叶子对应7次合并，每次比较3个字符，共21次字符相等比较。
5. 最大最小值算法每层只保存固定数量的数值；本实现的局部返回值是长度可能增长的字符串，切片产生的中间前缀也要计入空间。

相关学习：同时求数组的最大值与最小值、有序数组构造平衡二叉搜索树、递归与分治。