LeetCode 14 —— 最长公共前缀

题目链接

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 为字符串数组的规模，m 为 lcp 函数遍历的平均次数，故为 $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$ 这个规模就是我们要求解的子问题，而通过结合律有以下结论：

$LCP(S_1...S_n) = LCP(LCP(S_1...S_K), LCP(S_{k + 1}...S_n))$

每一个大问题都可以通过求解的中间值 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$ 次得： $k = 2 ^ {logn} = n$
- 推导得：$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]$ 范围中尝试寻找最大前缀长度的范围？

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

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

被确定为公共前缀，则让 low 指定到 mid 所在的位置缩小未知范围；
被确定不是公共前缀，则让 high 指定到 mid - 1 的位置缩小未知范围；
直到 low 和 hight 重叠或相交，数组中任何一个字符串的 $[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)$

LeetCode 14 —— 最长公共前缀

题目链接

题目描述

示例

题解

横向扫描

纵向扫描

分治策略

二分查找

大爷，赏口饭吃吧~