0014.最长公共前缀

难度：🟢 简单

标签：字符串、分治

链接：14. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

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

示例 2：

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

解题思路

核心思想

本题的核心是在一个字符串数组中，找到所有字符串都拥有的、最长的一个起始子串。

思路选择

纵向扫描法（逐列比较） 是解决此问题最高效的思路之一。我们以第一个字符串为基准，逐个检查它的每个字符，看这个字符是否也同时是其他所有字符串在对应位置上的字符。一旦遇到不匹配的情况，就可以立即确定最长公共前缀。

关键步骤

1. 处理边界情况：如果输入的数组为空，直接返回 ""。

2. 以第一个字符串为基准：外层循环遍历第一个字符串的每一个字符，索引为 i。

3. 验证所有字符串：内层循环遍历从第二个到最后一个的所有字符串，索引为 j。

4. 比较字符：在内层循环中，检查 strs[j] 在 i 位置的字符是否与 strs[0] 在 i 位置的字符相等。同时，也要处理 strs[j] 长度不足 i 的情况。

5. 返回结果：

   • 如果发现不匹配（字符不同或长度不足），说明最长公共前缀就是第一个字符串在 i 位置之前的部分，即 strs[0].substring(0, i)。

   • 如果外层循环正常结束，说明第一个字符串本身就是最长公共前缀，直接返回 strs[0]。

代码实现 (推荐)

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    // 处理边界情况
    if (!strs || strs.length === 0) {
        return "";
    }

    // 以第一个字符串为基准，逐字符构建前缀
    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];

        // 检查该字符是否为所有其他字符串在相同位置的字符
        for (let j = 1; j < strs.length; j++) {
            // 如果其他字符串更短，或者字符不匹配
            if (i === strs[j].length || strs[j][i] !== char) {
                // 返回当前已确认的公共前缀
                return strs[0].substring(0, i);
            }
        }
    }

    // 如果循环完成，说明第一个字符串本身就是最长公共前缀
    return strs[0];
};

原始代码分析 (用户提供)

您提供的解法也是一种有效的纵向扫描思路，通过逐个增加字符来构建前缀，并立即验证其有效性。这种方法思路清晰，但在性能上略有不同。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    // 初始化一个空字符串作为公共前缀
    let commonPrefix = '';
    // 以第一个字符串为基准进行遍历
    for (let i = 0; i < strs[0].length; i++) {
        // 每次循环，将第一个字符串的当前字符加入 commonPrefix
        commonPrefix += strs[0][i];
        // 遍历其余的字符串，进行验证
        for (let j = 1; j < strs.length; j++) {
            // 使用 indexOf 检查 commonPrefix 是否是当前字符串的前缀
            // 如果不是（返回值不为0），说明上一步加入的字符是多余的
            if (strs[j].indexOf(commonPrefix) !== 0) {
                // 去掉最后一个字符，并返回结果
                return commonPrefix.substr(0, commonPrefix.length - 1);
            }
        }
    }

    // 如果循环正常结束，说明第一个字符串本身就是最长公共前缀
    return commonPrefix;
};

• 优点：逻辑直观，一步步构建并验证。

• 潜在优化点：循环中频繁的字符串拼接 (+=) 和 indexOf 调用可能会比推荐解法中直接的字符比较 ([i]) 性能稍差，尤其是在字符串很长时。

复杂度分析

• 时间复杂度：O(S) 其中 S 是所有字符串中字符的总数。在最坏的情况下（所有字符串都相同），我们需要比较每个字符串的每个字符。最佳情况下，只需要比较 n * m 次，其中 n 是字符串数量，m 是最短字符串的长度。

• 空间复杂度：O(1) 我们只使用了常数个额外变量。

相关题目

• 0028.找出字符串中第一个匹配项的下标

• 0058.最后一个单词的长度

总结

本题是字符串处理的基础题，主要考察循环和字符串的基本操作。纵向扫描法（逐列比较）通常是效率最高的方法之一，因为它可以在发现第一个不匹配的字符时立即终止，避免了不必要的字符串比较。