最长公共前缀

题目

https://leetcode.cn/leetbook/read/array-and-string/ceda1/

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

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

实现

一、暴力搜索 + 计数统计

思路：从后向前遍历所有可能的前缀，统计每个前缀在字符串数组中出现的次数，最终找到满足条件的最长前缀。

1. 边界处理：

• 如果输入数组 strs 为空，直接返回空字符串 ""。
• 如果数组只有一个字符串，直接返回该字符串本身（因为无需比较）。

2. 预处理：

• 将字符串数组按长度升序排序，目的是以最短字符串为基准生成所有可能的前缀（减少无效比较）。

3. 初始化计数数组：

• 创建一个长度比最短字符串大 1 的数组 count，并初始化为 0。
  • 多出的一个长度是为了兼容最短字符串本身作为前缀的情况（例如 strs[0].slice(0, strs[0].length) 即完整字符串）。

4. 从后向前遍历所有可能的前缀：

• 对最短字符串 strs[0]，从完整长度开始逐步缩短（从后向前截取），生成子串 sub。
• 统计 sub 在数组中作为前缀出现的次数：
  • 遍历所有字符串，检查是否以 sub 开头，若是则计数 count[i]++。

5. 确定最长公共前缀：

• 从计数数组 count 的末尾向前查找第一个满足 count[i] === strs.length 的索引 i，表示所有字符串均以 strs[0].slice(0, i) 为前缀。
• 返回该子串作为结果。

6. 默认返回空字符串：

• 若没有满足条件的前缀，返回 ""。

// 暴力：从后向前遍历
var longestCommonPrefix1 = function (strs) {
    if (strs.length === 0) return '';
    if (strs.length === 1) return strs[0]; // 处理单个字符串的情况
 
    strs.sort((a, b) => a.length - b.length);
    let count = new Array(strs[0].length + 1).fill(0); // 增加一个长度以处理完整字符串
 
    for (let i = strs[0].length; i >= 0; i--) {
        let sub = strs[0].slice(0, i);
        for (let j = 0; j < strs.length; j++) {
            if (strs[j].startsWith(sub)) {
                count[i]++;
            }
        }
    }
 
    for (let i = count.length - 1; i >= 0; i--) {
        if (count[i] === strs.length) {
            return strs[0].slice(0, i);
        }
    }
 
    return '';
};

时间复杂度：排序 O(n log n) + 双层循环 O(m * n)：O(m + log n) 空间复杂度：计数数组 O(m) + 排序空间 O(log n)：O(m + log n)

二、优化：提前终止 + 去除排序

1. 提前终止：在统计 count[i] 时，若发现某个字符串不匹配当前 sub，可提前跳出内层循环。
2. 避免排序：直接以第一个字符串为基准，无需排序（但需处理基准字符串非最短的情况）。 修改后的代码：

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return '';
    const base = strs[0];
    for (let i = base.length; i >= 0; i--) {
        const sub = base.slice(0, i);
        if (strs.every(s => s.startsWith(sub))) {
            return sub;
        }
    }
    return '';
};

时间复杂度：

• 最坏情况：O(m * n)（m 是 base 的长度，n 是字符串数量）。
• 最佳情况：O(minLen * n)（快速找到短前缀）。

空间复杂度：O(1)（仅用常量空间）。

三、水平扫描

思路：逐个比较字符串，逐步缩小公共前缀的范围。

1. 假设第一个字符串 strs[0] 是最长公共前缀 LCP。
2. 遍历剩余字符串，不断调整 LCP，使其与当前字符串匹配。
3. 如果 LCP 变为空字符串，提前终止。

// 优化解法：水平扫描
var longestCommonPrefix = function (strs) {
    if (strs.length === 0) return '';
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, prefix.length - 1);
            if (prefix === '') return '';
        }
    }
    return prefix;
};

时间复杂度：

• 最坏情况：O(S)（S 是所有字符串的字符总数）。
• 最佳情况：O(minLen * n)。 空间复杂度：O(1)。