笔试题“14. 最长公共前缀”看起来是LeetCode上一道安静的基础题，但它实际上把字符串处理、边界意识、算法权衡、编码风格都揉在了一起。我在面试时也经常拿它考察候选人的基本功，看似人人会写，真正写得清爽又经得起追问的却不多。本文直接从题目出发，把解题思路、代码实现、复杂度分析和工程化思考一次讲透。
1. 题面与核心思路拆解
1.1 题目描述与名词澄清
题目本身一句话：给定一个字符串数组，返回所有字符串的公共前缀中最长的那一个；如果没有公共前缀，返回空字符串。
比如["flower", "flow", "flight"]，输出是"fl"；如果是["dog", "racecar", "car"]，三个字符串从头开始就没有相同的首字符，直接返回""。
很多新手在这里容易把“前缀”和“子串”混淆。前缀是严格从第一个字符开始连续截取的部分，比如"flow"是"flower"的前缀，但"low"不是。而子串可以是字符串中间的任意连续片段，两者完全是两个概念。题目限定了“前缀”，就意味着每一步比较都从第0位开始，这个问题因此会简单不少。
还有一个容易忽略的点：题目说的是“所有字符串”的公共前缀，不是两两之间最长前缀的简单叠加。两两之间算出的前缀，未必是全体的公共前缀。举例来说，"abc"和"abd"的最长公共前缀是"ab"，"ab"和"a"的公共前缀是"a"，但全体字符串的公共前缀还要先满足第三个字符串，所以必须保证每次结果都是跟剩余所有字符串对齐后的才有效。理解了这个约束，再去看各种解法，思路就顺了。
1.2 五种主流解法概览
这个题在社区里的热门解法大体有五种：横向扫描、纵向扫描、分治法、二分查找、字典树。每个方法都有自己擅长的场景和复杂度特征，先放一张对比表，后续一步一步展开。
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 横向扫描 | O(S)，S为所有字符总数 | O(1) | 最容易想到，适合快速写出正确代码 |
| 纵向扫描 | O(S)，最坏情况同样遍历全部字符 | O(1) | 代码精简，适合一次性通过所有边界测试 |
| 分治法 | O(S) | O(m log n)，m为最短串长度 | 适合面试展示递归拆解思维 |
| 二分查找 | O(S log m)，m为最短字符串长度 | O(1) | 适合数据量大、单个字符串较长且公共前缀较短的场景 |
| 字典树 | O(S) 构建，O(m) 查询 | O(S) | 适合多次查询、批量处理的前缀匹配场景 |
这里 S 表示全部字符串的字符总数。五种方法归根结底都在做同一件事：逐步缩小候选前缀的范围，只不过扫描顺序和剪枝策略不同。
2. 四种代码级解法实现与要点
2.1 横向扫描
横向扫描是最好理解的一种。拿第一个字符串作为初始候选前缀，用它和第二个字符串求公共前缀，得到的中间结果再和第三个字符串求公共前缀，一直迭代到最后一个字符串。中间如果公共前缀变成空串，说明后面不可能再出现非空公共前缀，可以直接返回。
def longest_common_prefix(strs: list[str]) -> str: if not strs: return "" prefix = strs[0] for s in strs[1:]: prefix = common_prefix(prefix, s) if prefix == "": return "" return prefix def common_prefix(a: str, b: str) -> str: i = 0 while i < len(a) and i < len(b) and a[i] == b[i]: i += 1 return a[:i]这段代码有两个细节值得注意。第一个是提前终止：prefix一旦为空，立刻返回，后面即使还有几百个字符串也不用再遍历了，这是横向扫描最主要的剪枝手段。第二个细节是common_prefix里的索引条件，i < len(a) and i < len(b)两者缺一不可，否则短字符串遍历完后继续访问b[i]就会越界。
在很多实战场景里，我还会额外加一个特判：如果数组中只有一个字符串，直接返回它本身，省掉一次无意义的比较计算。不过这个特判加不加都不影响正确性，横向扫描在单元素数组下也会返回strs[0]。
2.2 纵向扫描
纵向扫描的思路来得更直觉化。把所有字符串竖着排列，同一列字符逐个比对：先看所有字符串的第0位是否都相同，再看第1位是否都相同，一直往后推进，直到某一位出现不同或者某个字符串已经取完了，之前扫描过的列拼接起来就是答案。
def longest_common_prefix_vertical(strs: list[str]) -> str: if not strs: return "" for i in range(len(strs[0])): ch = strs[0][i] for s in strs[1:]: if i >= len(s) or s[i] != ch: return strs[0][:i] return strs[0]这段代码的终止条件写得比较紧凑：外层循环以第一个字符串的长度为准，内层循环判断其他字符串在当前位置是否越界或字符不一致。一旦触发终止条件，返回strs[0][:i]，也就是已经通过了所有字符串检查的前缀部分。
纵向扫描相比横向扫描有一个天然优势：它不需要维护中间变量，代码量少，且不需要如果公共前缀很短时会在很早期就退出。最坏情况下，比如所有字符串相同且很长，它确实会扫描完所有字符串的所有位置，复杂度为 O(S)。
有一个容易忽略的边界情况：如果第一个字符串本身是空串，外层range(len(strs[0]))根本不会执行，函数直接返回""，结果是正确的。如果数组整体为空，开头也做了返回，所以两条边界都覆盖到位了。
2.3 分治法
分治法把这个大问题拆成一个个小问题。将字符串数组从中间分割成左右两半，分别计算左右两部分的公共前缀，然后再对这两个结果求一次公共前缀，合并得到整个数组的答案。递归的终止条件是区间内只剩一个字符串时，直接返回它。
def longest_common_prefix_divide(strs: list[str], left: int, right: int) -> str: if left == right: return strs[left] mid = (left + right) // 2 lcp_left = longest_common_prefix_divide(strs, left, mid) lcp_right = longest_common_prefix_divide(strs, mid + 1, right) return common_prefix(lcp_left, lcp_right)调用方式是longest_common_prefix_divide(strs, 0, len(strs) - 1)。
分治法的核心收益在于逻辑上的独立性：左右两侧互不干扰，分别计算、最后合并，天然适合描述为并行任务。单线程下它并不会让时间复杂度假性下降，因为每个字符依然至多被比较一次，但递归解法在面试里能展示出你对“大问题拆小问题”的敏感度，这一点有时候比性能更打动人。
需要注意，递归的终止条件是left == right，如果传入一个空数组就会出问题。所以在分治入口处依然要先判断数组是否为空，这是递归解法摆脱不了的一层防御。
2.4 二分查找
二分查找的切入点比较巧妙。公共前缀的长度不可能超过数组中最短字符串的长度，所以只需要在[0, shortest_len]这个区间内二分搜索一个最长的可行前缀长度。所谓“可行”，就是前mid个字符构成的前缀被所有字符串共享。
def longest_common_prefix_binary(strs: list[str]) -> str: if not strs: return "" shortest_len = min(len(s) for s in strs) low, high = 0, shortest_len while low < high: mid = (low + high + 1) // 2 if is_common_prefix(strs, mid): low = mid else: high = mid - 1 return strs[0][:low] def is_common_prefix(strs: list[str], length: int) -> bool: prefix = strs[0][:length] for s in strs[1:]: if not s.startswith(prefix): return False return True二分模板里最容易写错的是mid = (low + high + 1) // 2这个细节。因为我们希望寻找“最大的可行长度”，属于典型的“找右边界”问题，所以中点要向上取整，避免在low和high相邻时陷入死循环。如果用(low + high) // 2，在某种边界下会永远停在同一个low上出不去。
这个解法的时间复杂度为 O(S log m)，其中 m 是最短字符串的长度。对于“字符串数量不多但单个字符串非常长，且公共前缀较短”的场景，它往往比横向扫描少做很多无效比较。不过日常编码中使用字符串切片时，需要留意 Python 的切片会创建新对象，如果 m 很大且每次都要切出前缀，内存开销会显著增加，底层更稳的做法是改成比较字符下标，不真正生成子串。
3. 字典树解法和面试进阶讨论
3.1 字典树建树与查询
字典树（Trie）提供了另一种持久化的视角。把所有字符串依次插入一棵前缀树，公共前缀就是这棵树中从根节点开始、只包含一个分支的深度。顺着根节点往下走，只要某个节点只有一个孩子，就说明所有字符串在这个位置上的字符依然一致，可以把这个字符加入答案；一旦遇到分支节点或叶子节点，就停止。
class TrieNode: def __init__(self): self.children = {} self.is_end = False def longest_common_prefix_trie(strs: list[str]) -> str: if not strs: return "" root = TrieNode() for s in strs: node = root for ch in s: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.is_end = True result = [] node = root while len(node.children) == 1 and not node.is_end: ch = next(iter(node.children)) result.append(ch) node = node.children[ch] return "".join(result)循环终止条件包含not node.is_end是个关键细节。如果某个字符串本身就是另一个字符串的前缀，比如数组是["ab", "a"]，根节点下的路径在字符a处已经是一个字符串的终点，此时虽然只有一个孩子，也不能继续往下走了，因为再往下取的"b"并不是所有字符串的公共前缀。
3.2 字典树的工程价值与空间成本
字典树在纯算法题里并不是最短的解法，但它有一个其他解法都没有的特性：建好树之后，任何新的字符串进来，都可以在 O(m) 时间内判断它和全体数据的最长公共前缀。横向扫描和纵向扫描每次都要从头跑一遍，而字典树支持重复查询。
代价是空间。每个节点都存一个哈希表，存储开销远高于数组本身。在实际工程中，如果字符串集合是一次性构建、后续查询很少，字典树不一定划算；但如果要做批量前缀匹配、自动补全、IP 路由表最长前缀匹配这类任务，字典树几乎是最标准的答案。
面试时候选人可以提一句：空间换时间，适合查询多、写入少的场景。这比单纯背一道题更能体现对数据结构本质的理解。
4. 边界条件测试与常见错误排查
4.1 边界用例速查表
这道题的正确性很大程度上取决于边界处理，我整理了一张常见测试用例表，建议写代码时逐条对照跑一遍。
| 输入 | 期望输出 | 说明 |
|---|---|---|
[] | "" | 空数组，所有解法都必须在入口处拦截 |
[""] | "" | 只有一个空串，最短长度就是 0 |
["abc"] | "abc" | 只有一个字符串，公共前缀就是它本身 |
["abc", "abc", "abc"] | "abc" | 所有字符串完全相同 |
["ab", "a"] | "a" | 某个字符串是另一个的前缀 |
["a", "ab", "abc"] | "a" | 最短字符串本身就是公共前缀 |
["racecar", "car"] | "" | 首字符都不相同 |
["", "abc"] | "" | 只要有一个空串，公共前缀必为空 |
4.2 新手最容易踩的四个坑
第一个坑是忘记空数组判断。很多横向扫描代码一开始就直接prefix = strs[0]，输入为空时立刻抛异常，面试现场写法上直接失分。
第二个坑是外层循环长度选错。纵向扫描里如果以最短字符串长度为基准，确实也能工作，但必须额外求一次最短长度；而直接以第一个字符串长度为基准更简单，内层再通过i >= len(s)做越界保护，逻辑反而更统一。
第三个坑是二分查找死循环。前面已经提过向上取整的问题，这是二分求右边界时最高频的失误。如果没意识到这一点，调试时很难发现为什么程序一直卡在某个长度上。
第四个坑是过早返回导致误判。分治法合并时，如果左右两边的公共前缀求得正确，合并不太容易出错；但横向扫描里如果拿了strs[0]和strs[-1]直接算公共前缀，就忽略了中国字符串，结果必然错误。这个反例在面试追问里经常出现，建议自己心里有个谱。
4.3 多语言实现差异提示
Python 写起来最顺手，但字符串不可变，频繁切片会有复制开销，纵向扫描直接比较字符索引的写法通常是最省内存的。用 Go 写横向扫描时，a[:i]切片是引用底层数组的，不会像 Python 那样立即复制，这让切片操作成本远低于 Python，但要注意切片持有的底层数组可能导致内存无法释放，长期运行的场景用string(a[:i])或先收集字节再转换更稳妥。Java 里substring在较新版本中也是复制字符数组的，大规模数据下尽量用StringBuilder逐步构建前缀，避免频繁创建中间字符串。
5. 复杂度计算分析与工程化思考
5.1 时间复杂度推导过程
设字符串数量为 n，最短字符串长度为 m，所有字符串总长度为 S。
横向扫描每轮都在缩短当前候选前缀，最坏情况下所有字符串内容完全一致，每轮都要把当前前缀完整比一遍，复杂度就是前缀长度 n 次累加，也就是 O(S)。纵向扫描最坏情况同样要比较每个字符串的每个字符，也是 O(S)。分治法的每一层合并操作，本质上也是在不重复或少量重复的情况下扫描字符，整体依然控制在 O(S)。二分查找每轮都要对所有字符串调用一次startswith检查，每轮检查成本是 O(n * mid)，总共 log m 轮，所以是 O(n * m * log m)，也就是 O(S log m)。字典树建树的插入成本是 O(S)，查询公共前缀时遍历深度最多为 m，所以是 O(S + m)。
| 解法 | 最坏时间复杂度 | 额外空间 | 是否支持流式输入 |
|---|---|---|---|
| 横向扫描 | O(S) | O(1) | 不支持，依赖第一个字符串做初始值 |
| 纵向扫描 | O(S) | O(1) | 部分支持，逐列检查天然适合逐行读取 |
| 分治法 | O(S) | O(m log n) | 不支持，需要完整数组分片 |
| 二分查找 | O(S log m) | O(1) | 不支持，需要最短长度 |
| 字典树 | O(S + m) | O(S) | 支持，可以边插入边查询 |
5.2 从算法题延伸到真实系统设计
公共前缀计算并不只是刷题用。比如在一个日志分析系统里，需要从几十万条 SQL 语句中统计共同的查询前缀，找出模式化访问的流量特征；又比如在做批量文件同步时，要计算所有文件路径的最长公共目录，决定从哪里开始打包；再比如网络设备做路由聚合时，IP 前缀的最长匹配本质上就是公共前缀问题在二进制空间里的变体。
我见过一个真实案例：某团队要在一批序列化数据里提取冗余字段路径，数据量很大，字符串长度平均几百字节。他们最初用横向扫描，因为大多数记录在第二个字段位就出现差异，整体表现还好。后来数据源格式变了，很多记录共享了非常长的前半段，横向扫描的耗时立刻上升。替换成二分查找后，查询次数从“逐字符扩散”变成“按长度跳跃”，在共享前缀很长、整体数据量大的场景下提速非常明显。这说明同一个算法在不同数据特征下会有完全不同的表现，理解数据形态比背时间复杂度更重要。
5.3 面试追问与思路升华
面试官在这道题上最常见的追问是：如果字符串数量巨大，内存放不下怎么办？这个问题可以这样回答：逐列扫描天然支持流式读取，每次只比较一个字符，不需要把所有字符串一次性载入内存。字典树虽然查询能力强，但构建时需要访问全部数据，流式场景反而不好做。所以“数据规模”和“内存上限”会直接决定你选择哪个方案。
另一个追问是：如果求的不是单个字符串数组的公共前缀，而是动态追加新字符串时要实时维护公共前缀，你会怎么设计？这时候可以用字典树思想维护一个计数器，每个节点记录经过该节点的字符串数量，当已有 N 个字符串时，如果当前节点计数等于 N，则说明该字符对所有字符串都出现，可以计入公共前缀；一旦计数小于 N，就停止。这种扩展设计说明你不只是背了一个模板，而是真的理解了公共前缀的数据结构本质。
6. 写在最后
这道题我刷过不止一遍，每次重做都有新体会。早期我只追求“AC”，后来开始对比不同解法在极端输入下的表现，再后来把它搬到了分布式日志解析的场景里，才发现算法题和工程实践之间的连接点其实比想象中多得多。
个人经验是：如果时间紧迫，优先把纵向扫描写得滚瓜烂熟，它代码短、边界意识强、不需要额外空间，适合作为面试时的默认答案。如果聊到优化，再引出二分查找或字典树，这会显得你的知识是有层次的，而不是一味堆解法。最后一个小技巧，写完后用前面那张边界用例表过一遍，尤其是["", "abc"]和["ab", "a"]这两条，能防住绝大多数隐藏 bug。
