Python · 3 分钟阅读

14：最长公共前缀

题目
- 示例
- 约束
方法概览
方法一：水平扫描（最常用）
- 复杂度
方法二：垂直扫描
方法三：zip + set（Pythonic）
方法四：分治
方法五：二分
测试用例
方法对比
易错点

题目

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

示例

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

输入: strs = ["dog", "racecar", "car"]
输出: ""
解释: 输入不存在公共前缀。

约束

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

方法概览

方法	思路	备注
水平扫描	拿第一个串做候选，逐个缩短	简单直接
垂直扫描	按列比较，遇到不匹配立即返回	直观但要遍历字符
`zip` 法	`zip(*strs)` + `set` 去重	Pythonic 写法
分治	拆两半分别求前缀，再合并	适合并行/递归练习
二分	在最短字符串长度上做二分	面试加分项

方法一：水平扫描（最常用）

from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        # 以第一个串为基准
        prefix = strs[0]
        for s in strs[1:]:
            # 不断缩短 prefix，直到它成为 s 的前缀
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix

复杂度

最坏时间：O(S)，其中 S = sum(len(s) for s in strs)，因为每个串最多被扫到公共前缀长度那么多次。
空间：O(1)（除了输入）。

方法二：垂直扫描

from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        min_len = min(len(s) for s in strs)

        for i in range(min_len):
            ch = strs[0][i]
            if any(s[i] != ch for s in strs):
                return strs[0][:i]
        return strs[0][:min_len]

思路：按列比较所有串的第 i 个字符；遇到第一个不匹配就立刻返回前缀。

方法三：`zip` + `set`（Pythonic）

from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        prefix = []
        for chars in zip(*strs):
            # zip 会以最短串为准截断，超过最短串长度的字符不会被比较
            if len(set(chars)) == 1:
                prefix.append(chars[0])
            else:
                break
        return "".join(prefix)

要点：zip(*strs) 每次返回“一列字符”，用 set 去重后如果长度为 1，就说明
这一列全部相同。

zip 不会抛异常，越界时直接停止产出，所以边界安全。

方法四：分治

from typing import List


def longest_common_prefix(left: str, right: str) -> str:
    # 逐步缩短 left，直到它是 right 的前缀
    while not right.startswith(left):
        left = left[:-1]
        if not left:
            return ""
    return left


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        def divide(l: int, r: int) -> str:
            if l == r:
                return strs[l]
            mid = (l + r) // 2
            left = divide(l, mid)
            right = divide(mid + 1, r)
            return longest_common_prefix(left, right)

        return divide(0, len(strs) - 1)

分治版用于练习“递归 + 归并”思路，时间仍是 O(S)，但能体现分治思想。

方法五：二分

from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        low, high = 0, min(len(s) for s in strs)

        while low < high:
            mid = (low + high + 1) // 2   # 上中位
            if self._is_prefix(strs, mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

    def _is_prefix(self, strs: List[str], length: int) -> bool:
        prefix = strs[0][:length]
        return all(s.startswith(prefix) for s in strs)

把问题转化为：前 length 个字符是否在所有串中相同？对 length 做二分，
时间仍是 O(S log L)，但当 S 特别大且 L 适中时，思路更优雅。

测试用例

def test():
    s = Solution()
    assert s.longestCommonPrefix(["flower", "flow", "flight"]) == "fl"
    assert s.longestCommonPrefix(["dog", "racecar", "car"]) == ""
    assert s.longestCommonPrefix([]) == ""
    assert s.longestCommonPrefix([""]) == ""
    assert s.longestCommonPrefix(["abc"]) == "abc"
    assert s.longestCommonPrefix(["ab", "a"]) == "a"
    assert s.longestCommonPrefix(["a", "b"]) == ""
    print("all passed")


test()

方法对比

方法	优点	缺点	推荐
水平	简单、稳定	字符串拼接略多	★★★
垂直	直观、容易讲清楚	略多 if	★★
`zip`	短、Pythonic	依赖 zip 行为	★★
分治	训练递归思维	代码多	★
二分	训练二分思维	复杂度略高	★

易错点

空数组 或数组里出现空串时，要返回 ""，不是 None。
不要假设第一个串就是答案；要 逐个验证。
注意 zip 的“按最短串截断”特性，避免手动 min。