BM84　最长公共前缀¶

简单通过率 30.75%python3核心代码模式样例通过牛客 AC字符串

牛客原题　源码

讲解章节：字符串处理

一句话

以第一个串为标尺纵向扫描，某一列出现分歧就在这里截断。

解题思路¶

这题考什么¶

一条把搜索空间压成一维的观察：公共前缀一定是任意一个串的前缀，于是拿 strs[0] 当标尺，答案只可能是它的某个前缀，问题就退化成「这个前缀最长能到第几列」，只剩一个截断点要找。

纵向扫描：固定列号 j，把所有串的第 j 个字符比一遍。

strs = ["abca", "abc", "abca", "abc", "abcc"]

j=0   a a a a a      全同，继续
j=1   b b b b b      全同，继续
j=2   c c c c c      全同，继续
j=3   a ✗            strs[1] 只有 3 个字符，越界 -> 停在 j=3

两种停机条件缺一不可：

* 某个串已经走完（j == len(strs[i])），前缀不可能再长
* 某个串第 j 位与标尺不同

停下来时 j 恰好等于「已确认全同的列数」，返回 strs[0][:j]。

横向扫描是另一种常见写法：先令 ans = strs[0]，逐个串把 ans 削短到它与该串的公共前缀。最坏复杂度相同，但每削一次都要新建一个字符串对象，常数更大，也拿不到「空间 O(1)」。

数据规模与复杂度¶

n <= 5000、单串长度 <= 5000，时限「其他语言 2 秒」。纵向扫描的最坏情形是所有串完全相同，比较 n * len = 2.5e7 次字符；一旦出现分歧立刻返回，实际远小于此。空间 O(1)：全程只有几个下标，切片只在返回那一次发生，正好对上题面「空间复杂度 O(1)」的进阶要求。

坑在哪¶

strs 为空数组要先挡住（题面允许 n = 0），否则 strs[0] 直接 IndexError。
内层判断必须先测 j >= len(s) 再取 s[j]。Python 的 or 是短路的，顺序颠倒会在短串上抛越界异常，而不是正确地把前缀截断在这里。
任一串是空串时不需要额外特判：第一轮 j = 0 就因为 0 >= len(s) 停下，返回 first[:0] 即空串。
返回的切片右端是 j 而不是 j + 1 或 j - 1。j 是已确认全同的列数，而切片右端为开区间，first[:j] 的长度恰好就是 j。
外层循环走完没有返回，说明标尺整根都没被截断——它本身就是公共前缀，此时要返回 first 而不是空串。

参考实现¶

solutions/nowcoder/BM84/sol.py
from typing import List, Optional


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 题面允许 n = 0，先挡住空数组，否则下面取 strs[0] 会越界
        if not strs:
            return ""

        first = strs[0]                 # 标尺：答案必是它的某个前缀
        # 纵向扫描：j 为当前比对的列号，first[:j] 是已确认全同的部分
        for j in range(len(first)):
            c = first[j]
            for s in strs:
                # 短路顺序不能反：先确认第 j 位存在，再取来比较。
                # 越界与分歧都说明公共前缀止于第 j 列，切片右端开区间正好取 j 个字符
                if j >= len(s) or s[j] != c:
                    return first[:j]
        # 标尺整根走完都没被截断，它自己就是最长公共前缀
        return first

BM84 最长公共前缀¶