python必背源代码最长公共前缀代码

Alice
Alice
发布时间:2026-11-20| 4人浏览过
原创

深入解析Python实现最长公共前缀的经典必背源代码。包含纵向扫描法、字典序极值法与横向扫描法的完整实现、逐行推导、图解流程与复杂度对比。

主题:Python 经典算法精讲 核心算法:最长公共前缀 (LeetCode 14) 重点:纵向扫描 · 字典序极值法
最长公共前缀(Longest Common Prefix)问题是指在给定的字符串列表中,找出所有字符串都包含的最长起始子串。解决该问题的标准解法主要有两类:一类是逐列比对的纵向扫描法(时间复杂度最优且支持早停),另一类是利用 Python 语言特性的字典序极值法(代码极其凝练)。掌握这两套必背源码及其边界处理,是熟练应对 Python 字符串算法面试与日常文本清洗的基础。
python必背源代码最长公共前缀代码
图 0:最长公共前缀问题的字符矩阵对齐与分歧点判定

一、问题定义与核心逻辑

在字符串处理任务中,最长公共前缀的判定规则可以严格表述为:给定一个字符串数组 strs,寻找一个尽可能长的字符串 P,使得数组中的每一个字符串 s 均满足 s.startswith(P)。若列表为空或任意两个字符串的第一个字符便不相同,则公共前缀为空字符串 ""。

该问题的两个极端边界情况尤为值得注意:

  • 空输入或单元素:若输入列表为空列表 [],直接返回 "";若列表仅含一个字符串(如 ["single"]),其最长公共前缀必然是自身。
  • 提前分歧:只要列表中存在某一个字符串已遍历结束,或者任意两个字符串在同一列出现不同字符,搜索就必须立刻终止。
python必背源代码最长公共前缀代码
图 1:横向扫描(串联推进)与纵向扫描(按列对齐)的机制对比

二、必背源码一:标准纵向扫描法

纵向扫描法是面试与生产中最推荐的标准代码。它的核心思想是:以第一个字符串 strs[0] 作为基准标尺,逐列检查所有其他字符串对应下标的字符是否一致。

1. 完整实现源码

def longest_common_prefix_vertical(strs: list[str]) -> str:
    # 1. 边界检查:若列表为空,直接返回空字符串
    if not strs:
        return ""

    # 2. 以首个字符串为基准,遍历其每个字符与索引
    for i in range(len(strs[0])):
        ch = strs[0][i]
        
        # 3. 纵向检查后续每一个字符串在当前列 i 的字符
        for s in strs[1:]:
            # 条件一:当前字符串长度不足 i(已到结尾)
            # 条件二:当前字符串在 i 处的字符与基准字符不匹配
            if i == len(s) or s[i] != ch:
                return strs[0][:i]

    # 4. 若首个字符串全部字符均通过校验,则其本身就是最长公共前缀
    return strs[0]

2. 运行示例

# 示例调用
data_1 = ["flower", "flow", "flight"]
data_2 = ["dog", "racecar", "car"]

print(longest_common_prefix_vertical(data_1))  # 示例输出: fl
print(longest_common_prefix_vertical(data_2))  # 示例输出: ""

3. 逐行执行细节与注意事项

在这段代码中,最关键的是内层判断 if i == len(s) or s[i] != ch: 的书写顺序。

避坑警示:短路求值顺序不可调换
必须先判断 i == len(s),后判断 s[i] != ch。因为当某个字符串 s 比基准串更短时,如果颠倒顺序直接执行 s[i],将立即引发 Python 的 IndexError: string index out of range 异常。利用 Python 的 or 短路特性,可以在下标越界前安全截断并返回。
python必背源代码最长公共前缀代码
图 2:纵向扫描核心流程与条件分支控制图

三、必背源码二:字典序极值法

在 Python 面试中,若想要展现对语言内建函数与字符串排序特性的深度理解,字典序极值法(min/max 法)是最具技巧性与美感的高效解法。

1. 完整实现源码

def longest_common_prefix_minmax(strs: list[str]) -> str:
    # 1. 边界检查
    if not strs:
        return ""

    # 2. 获取整个列表中字典序最小和最大的两个字符串
    s_min = min(strs)
    s_max = max(strs)

    # 3. 仅比对极小串与极大串的公共字符
    for i, ch in enumerate(s_min):
        if ch != s_max[i]:
            return s_min[:i]

    # 4. 若全部匹配,s_min 即为公共前缀
    return s_min

2. 为什么只需比对 min 和 max?

初学者往往会对这套解法产生疑问:为什么跳过了列表内部的所有其他字符串,仅比对两个极值就能代表整个数组?

其数学与逻辑依据在于字符串在 ASCII / Unicode 编码下的全序性(字典顺序)。设想我们将整个列表的所有字符串按字典序从小到大排列:如果某个前缀存在分歧,那么最先产生分歧的一定位于字典序两端(最左端的 s_min 与最右端的 s_max)。换言之,排在中间的所有字符串,其对应位置的字符编码值必然被夹在 s_min 与 s_max 之间。如果 s_min[i] == s_max[i],中间所有字符串在下标 i 处的字符必然也是同一个字符。

python必背源代码最长公共前缀代码
图 3:字典序极值法的前缀包含性与数学逻辑推导

四、进阶与拓展写法:横向扫描与 zip 压缩

1. 横向扫描法(两两规约)

横向扫描法采用迭代更新公共前缀的方式,先将 prefix = strs[0],然后用它依次与 strs[1]、strs[2] 进行比对并不断缩短 prefix:

def longest_common_prefix_horizontal(strs: list[str]) -> str:
    if not strs:
        return ""

    prefix = strs[0]
    for s in strs[1:]:
        # 当 s 不是以当前 prefix 开头时,不断切掉末位字符
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

2. Pythonic 的 zip 与 set 语法糖解法

利用 Python 内置的 zip(*strs) 可以极其优雅地将多个字符串“解压并按列打包”,结合 set 去重,可以写出极富 Python 风格的纵向扫描:

def longest_common_prefix_zip(strs: list[str]) -> str:
    if not strs:
        return ""

    res = []
    # zip(*strs) 会按列同步打包,以最短字符串长度自动终止
    for col in zip(*strs):
        if len(set(col)) == 1:
            res.append(col[0])
        else:
            break
    return "".join(res)

注意:zip(*strs) 会自动在最短字符串结束时停止迭代,因此完全规避了下标越界问题。但在空间上,set(col) 会产生微小的集合开销。

五、算法复杂度与选型总结

下表系统梳理了四种常见最长公共前缀实现的复杂度及适用场景(设 $N$ 为字符串总数量,$M$ 为最短字符串长度,$S$ 为全部字符串字符总数):

python必背源代码最长公共前缀代码
图 4:最长公共前缀主流算法特性与适用选型矩阵

选型建议与总结

在实际编程与面试中,可以依据具体侧重点进行选择:

  • 面试现场手撕:首选标准纵向扫描法。该解法不依赖特定语言的高级黑盒,严格展示了双重循环控制、越界防范与短路判断,是算法面试中最稳妥、得分率最高的实现。
  • 工程极简或 Python 特色展现:选择字典序极值法(min/max)。仅需提取首尾两个极值并进行单次比对,代码仅有寥寥数行,既展现了算法深度,又体现了对 Python 语言内部机制的娴熟驾驭。
相关专题:

免责声明:本文内容仅供参考,不代表本站观点。转载或引用请注明出处。

Python 相关产品和应用

全部下载
Selenium

Selenium

4.51.0 · Windows

用于浏览器自动化和 Web 测试的 Python 工具。

scikit-learn

scikit-learn

1.9.1 · Windows

常用 Python 机器学习算法与模型评估工具库。

Black

Black

26.10.1 · Windows

强调一致性的 Python 自动代码格式化工具。

Ruff

Ruff

0.17.1 · macOS

由 Rust 编写的高速 Python 代码检查和格式化工具。

pytest

pytest

9.1.1 · Windows

简洁而强大的 Python 自动化测试框架。

FastAPI

FastAPI

0.146.0 · Windows

高性能 Python API 框架,支持类型提示和自动接口文档。

Flask

Flask

3.1.3 · Windows

轻量灵活的 Python Web 应用框架。

Django

Django

6.1.2 · Windows

成熟的 Python Web 框架,适合构建内容站点和业务系统。

Spyder

Spyder

6.1.7 · Windows

面向科学计算与数据分析的 Python 集成开发环境。

SciPy

SciPy

1.18.1 · Windows

面向科学、工程和技术计算的 Python 算法库。