题目链接

https://leetcode-cn.com/problems/longest-common-prefix/

题目描述

编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串 ""

示例

示例 1:

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

示例 2:

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

题解

横向扫描

横向比较的思路就是我们每次传入两个字符串对比,得到这两项的公共前缀,再拿得到的结果和下一个字符串对比,直到所有字符串都对比完得到最大公共前缀。

$LCP(S_1…S_n) = LCP(LCP(LCP(LCP(S_1, S_2), S_3), S_4), …S_n)$


横向扫描示意图
横向扫描示意图


根据示意图可以知道,我们首先应该用一个变量存储 LCP 过程的结果,默认为字符串数组的第一项,并遍历字符串数组,用当前的公共前缀去和每一项字符串对比得出新的公共前缀。

在获取两个字符串公共前缀的过程中需要遍历字符串,所以当遍历次数达到较短的字符串长度时,或者出现某次遍历字符串对应位置上两个字符不相等时,则可以停止遍历得出当前的公共前缀,当所字符串数组遍历完可以得出最终的公共前缀并返回。

const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return '';

  const lcp = (str1, str2) => {
    const length = Math.min(str1.length, str2.length);
    let index = 0;

    while (index < length && str1[index] === str2[index]) {
      index++;
    }

    return str1.slice(0, index);
  }

  return strs.reduce((prev, next) => lcp(prev, next));
}

复杂度分析:

  • 时间复杂度:n 为字符串数组的规模,mlcp 函数遍历的平均次数,故为 $O(m * n)$
  • 空间复杂度:$O(1)$

纵向扫描

相比于横向扫描,整个字符串为维度两两求公共前缀,纵向扫描是以每一个字符为维度的遍历,最后得到公共前缀,我们也可以把字符串的看做一个不规则的表格,每个字符代表一个单元格。


纵向扫描示意图
纵向扫描示意图


在每次一个字符一个字符的比对时,当有内层遍历一个字符串对应位置的字符与其他不符合,或者外层遍历到最短的那个字符串时结束。

const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return '';

  const len = strs.length;
  const count = strs[0].length;

  for (let i = 0; i < count; i++) {
    for (let j = 0; j < len; j++) {
      if (i === strs[j].length || strs[0][i] !== strs[j][i]) {
        return strs[0].slice(0, i);
      }
    }
  }

  return strs[0];
}

复杂度分析:

  • 时间复杂度:n 为字符串数组的规模,m 字符串的平均长度,故为 $O(m * n)$
  • 空间复杂度:$O(1)$

分治策略

分治算法满足的条件:

  • 分解:将要解决的问题划分成规模更小的问题;
  • 求解:将划分的足够小的子问题用相对简单的方法解决;
  • 合并:按照原问题的要求将子问题的解逐层合并为原问题的解。

通过横向扫描法我们可以知道两个字符串可以求解公共前缀,$n = 2$ 这个规模就是我们要求解的子问题,而通过结合律有以下结论:


分治策略示意图
分治策略示意图


每一个大问题都可以通过求解的中间值 mid 范围划分为两个子问题 $LCP(S_1…S_mid)$$LCP(S_{mid + 1}…S_n)$,子问题继续划分为两个子问题,依次类推,划分到最小颗粒度为止(范围内不大于两个字符串求解),再通过子问题得到的结果逐级合并,所以使用递归回溯更适合解决分治的问题。

const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return '';

  const commonPrefix = (lcpLeft, lcpRight) => {
    const len = Math.min(lcpLeft.length, lcpRight.length);

    for (let i = 0; i < len; i++) {
      if (lcpLeft[i] !== lcpRight[i]) {
        return lcpLeft.slice(0, i);
      }
    }

    return lcpLeft.slice(0, len);
  }

  const lcp = (start, end) => {
    if (start === end) return strs[start];

    const mid = Math.floor((start + end) / 2);
    return commonPrefix(lcp(start, mid), lcp(mid + 1, end));
  }

  return lcp(0, strs.length - 1);
}

复杂度分析:

  • 时间复杂度:通过分治策略的递推公式 $T(n) = k * T(n / k) + O(n - 1)$
    • 其中每个问题每次分治的子问题数为 2
    • 分治 $logn$ 次得:
    • 推导得:$T(n) = n * T(1) + O(n - 1) = O(n) + O(n - 1) = O(n)$
    • 因每次子问题执行复杂度为 $O(m)$m 为字符串平均长度,最终可推出时间复杂度为 $O(m * n)$
  • 空间复杂度:主要取决于递归调用的次数,故为 $O(logn)$

二分查找

寻找最大公共前缀的过程中有一点在其他的实现方式中也有应用,就是最大前缀的长度一定不会超过最短的字符串的长度,那是不是可以高效的在 $[0, minLength]$ 范围中尝试寻找最大前缀长度的范围?

我们粗略的把最短的字符串不断的分成两个范围,一个是已经确定是公共前缀的范围,一个是未确定公共前缀的范围,然后不断的去在未确定公共前缀的范围中寻找边界,不断的缩短未知的范围直到找到最大公共前缀。


二分查找示意图
二分查找示意图


此时我们就可以通过二分查找法来实现,设置变量 lowhigh 指向未知范围的起点和终点,通过起点终点求出中间点 mid,此时两个范围 $[low, mid)$$[mid, high)$

  • 被确定为公共前缀,则让 low 指定到 mid 所在的位置缩小未知范围;
  • 被确定不是公共前缀,则让 high 指定到 mid - 1 的位置缩小未知范围;
  • 直到 lowhight 重叠或相交,数组中任何一个字符串的 $[0, low)$ 就是最大公共前缀。
const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return '';

  const isCommonPrefix = (strs, len) => {
    const [first, ...other] = strs;
    return other.every((str) => first.slice(0, len) === str.slice(0, len));
  }

  let low = 0;
  let high = strs.reduce((min, str) => Math.min(min, str.length), Infinity);

  while (low < high) {
    const mid = Math.ceil((low + high) / 2);

    if (isCommonPrefix(strs, mid)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }

  return strs[0].slice(0, low);
}

复杂度分析:

  • 时间复杂度:n 为字符串数组的规模,m 字符串的平均长度,二分查找迭代次数为 $O(logm)$,每次判断是否是公共前缀需要执行 $O(m * n)$ 次,故为 $O(mnlogm)$
  • 空间复杂度:$O(1)$