最长公共前缀（Longest Common Prefix）问题 问题描述 给定一个字符串数组，要求找出这些字符串的 最长公共前缀 。最长公共前缀是指所有字符串都共有的、从第一个字符开始的最长连续子串。如果不存在公共前缀，则返回空字符串。 示例 输入： ["flower", "flow", "flight"] 输出： "fl" 输入： ["dog", "racecar", "car"] 输出： "" 解题思路 这个问题可以通过多种方法解决，我将介绍三种经典方法，并详细解释最直观的 水平扫描法 。 方法一：水平扫描法（逐字符比较） 核心思想 ：以第一个字符串为基准，依次将其每个字符与其他字符串的对应位置字符进行比较。一旦发现不匹配或某个字符串已遍历完，就停止并返回当前已匹配的前缀。 详细步骤 ： 边界情况处理 ： 如果数组为空，直接返回空字符串 "" 。 如果数组只有一个字符串，那么它自身就是最长公共前缀，直接返回该字符串。 选取基准字符串 ： 通常选择第一个字符串作为基准，记为 prefix 。 逐字符比较 ： 从第一个字符开始（索引 i = 0 ），遍历 prefix 的每个字符。 对于当前字符位置 i ，依次检查数组中 其他每个字符串 在位置 i 的字符。 比较条件： a. 如果某个字符串的长度等于 i （即已到该字符串末尾），说明该字符串已经被完全匹配，此时最长公共前缀就是该字符串本身，因此停止并返回当前已匹配的子串。 b. 如果某个字符串在位置 i 的字符与 prefix[i] 不同，说明不匹配，停止并返回当前已匹配的子串。 如果所有字符串在位置 i 的字符都相同，则将该字符加入公共前缀，继续检查下一个位置。 返回结果 ： 遍历完成后，返回累积的公共前缀。 例子演示 ： 输入： ["flower", "flow", "flight"] 初始 prefix = "flower" ，但注意我们不会直接修改它，而是动态构建结果。 比较位置 0：所有字符串的第一个字符都是 'f' ，匹配。 比较位置 1：所有字符串的第二个字符都是 'l' ，匹配。 比较位置 2： "flower"[2] = 'o' "flow"[2] = 'o' "flight"[2] = 'i' 发现 'o' 与 'i' 不匹配，停止。 返回前 2 个字符组成的子串： "fl" 。 时间复杂度 ：O(S)，其中 S 是所有字符串中字符的总数。最坏情况下，需要比较所有字符串的每个字符。 空间复杂度 ：O(1)，只使用了常数额外空间。 方法二：垂直扫描法（按字符串顺序比较） 核心思想 ：不依赖基准字符串，而是 同时遍历所有字符串的相同位置 。 步骤 ： 找到数组中最短字符串的长度 minLen 。 从索引 0 到 minLen-1 ，依次比较所有字符串在当前索引的字符。 一旦发现不匹配，立即返回当前已匹配的前缀。 如果全部匹配，则返回最短字符串本身。 优缺点 ：与方法一类似，但在某些情况下可能提前停止（例如最短字符串很短时）。 方法三：分治法 核心思想 ：将数组分成两半，分别找出左半部分和右半部分的最长公共前缀，然后合并两个结果（即找出这两个前缀的公共前缀）。 步骤 ： 将数组递归地分成更小的子问题，直到子问题中只有一个字符串（其公共前缀就是自身）。 逐层合并：比较两个子结果的公共前缀，找出它们的新公共前缀。 递归合并完成后，得到最终结果。 时间复杂度 ：O(S)，其中 S 是所有字符串的字符总数。分析稍复杂，但性能与水平扫描相当。 空间复杂度 ：O(log n) 用于递归调用栈，其中 n 是字符串数量。 方法四：二分查找法 核心思想 ：对 可能的最长公共前缀长度 进行二分查找。 步骤 ： 找到数组中最短字符串的长度 minLen 。 在区间 [0, minLen] 中进行二分查找： 取中间值 mid ，检查所有字符串的前 mid 个字符是否相同。 如果相同，说明公共前缀长度至少为 mid ，可以尝试更长的前缀（向右搜索）。 如果不相同，说明公共前缀长度小于 mid ，应缩短长度（向左搜索）。 二分查找结束时，得到最大匹配长度，返回对应子串。 时间复杂度 ：O(S * log m)，其中 m 是最短字符串长度。每次检查需要 O(S) 时间。 适合场景 ：当字符串非常长时，二分查找可以减少比较次数。 总结 水平/垂直扫描法 直观且易于实现，是面试中最常见的方法。 分治法 适合并行计算或作为递归思维的练习。 二分查找法 在字符串很长时有性能优势。 在实际面试中，通常只需详细阐述 水平扫描法 的实现，并简要提及其他方法以展示知识广度。