algorithms►leetcode

030-最长公共前缀

14.最长公共前缀问题-Easy

问题描述

给定一个字符串数组 strs，找出所有字符串的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例

1
2
3
4
5
输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""

方法一：水平扫描法（逐字符比较）

核心思想

  1. 以第一个字符串为基准。
  2. 逐个字符与其他字符串的对应位置比较。
  3. 遇到不匹配时停止，返回当前匹配的前缀。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    let prefix = strs[0]; // 初始化为第一个字符串
    
    for (let i = 1; i < strs.length; i++) {
        //用startsWith更直观： !strs[i].startsWith(prefix)
        while (strs[i].indexOf(prefix) !== 0) { // 检查当前字符串是否以prefix开头
            prefix = prefix.slice(0, prefix.length - 1); // 缩短prefix
            if (prefix === "") return ""; // 提前终止
        }
    }
    
    return prefix;
};

复杂度分析

  • 时间复杂度：O(S)，其中 S 是所有字符串的字符总数。
  • 空间复杂度：O(1)。

方法二：垂直扫描法（逐列比较）

核心思想

  1. 按列比较所有字符串的相同位置字符。
  2. 遇到不匹配时停止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var longestCommonPrefix = function(strs) {
    if (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].slice(0, i); // 返回当前匹配的前缀
            }
        }
    }
    
    return strs[0]; // 全部字符匹配
};

复杂度分析

  • 时间复杂度：O(S)，最坏情况下需要比较所有字符。
  • 空间复杂度：O(1)。

方法三：分治法

核心思想

  1. 将问题分解为子问题：分别求左半部分和右半部分的最长公共前缀。
  2. 合并子问题的解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    return divideAndConquer(strs, 0, strs.length - 1);
};

function divideAndConquer(strs, left, right) {
    if (left === right) return strs[left];
    
    const mid = Math.floor((left + right) / 2);
    const leftPrefix = divideAndConquer(strs, left, mid);
    const rightPrefix = divideAndConquer(strs, mid + 1, right);
    
    return commonPrefix(leftPrefix, rightPrefix);
}

function commonPrefix(str1, str2) {
    const minLen = Math.min(str1.length, str2.length);
    for (let i = 0; i < minLen; i++) {
        if (str1[i] !== str2[i]) {
            return str1.slice(0, i);
        }
    }
    return str1.slice(0, minLen);
}

复杂度分析

  • 时间复杂度：O(S)，其中 S 是所有字符串的字符总数。
  • 空间复杂度：O(m log n)，递归调用栈的深度。

方法四：二分查找法

核心思想

  1. 对最短字符串的长度进行二分查找。
  2. 检查当前长度是否是所有字符串的公共前缀。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    let minLen = Math.min(...strs.map(s => s.length));
    let low = 1, high = minLen;
    
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (isCommonPrefix(strs, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return strs[0].slice(0, (low + high) / 2);
};

function isCommonPrefix(strs, len) {
    const prefix = strs[0].slice(0, len);
    for (let i = 1; i < strs.length; i++) {
        if (!strs[i].startsWith(prefix)) {
            return false;
        }
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(S log m)，其中 m 是最短字符串的长度。
  • 空间复杂度：O(1)。

方法对比

方法 时间复杂度 空间复杂度 适用场景
水平扫描 O(S) O(1) 通用
垂直扫描 O(S) O(1) 字符较短时
分治法 O(S) O(m log n) 大规模数据
二分查找 O(S log m) O(1) 字符串较长时

边界情况处理

  1. 空数组：直接返回 ""。
  2. 单字符串：返回该字符串本身。
  3. 完全匹配：返回最短字符串。

总结

  • 推荐方法：垂直扫描法（代码简洁，效率高）。
  • 优化选择：如果字符串非常长，考虑二分查找法。
  • 分治法的优势：适合分布式计算或超大规模数据。