【算法篇】求最长公共前缀JavaScript版本

题目描述

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围：
数据范围:0<n<5000，0<len(strsi)< 5000
进阶:空间复杂度 O(1)，时间复杂度 O(n*len)

示例1

输入：[“abca”,“abc”,“abca”,“abc”,“abcc”]
返回值：“abc”

示例2

输入：[“abc”]
返回值：“abc”

解题思路

方法一：水平扫描法

1. 初始化：首先检查输入数组是否为空，如果为空则直接返回空字符串。如果只有一个字符串，则返回该字符串本身，因为这时最长公共前缀就是这个字符串。

2. 迭代比较：将第一个字符串作为初始的最长公共前缀。然后遍历数组中的其他字符串，对每个字符串使用indexOf方法检查当前公共前缀是否存在于该字符串中。

3. 缩短当前公共前缀：如果发现当前公共前缀不在某个字符串中，就将公共前缀缩短一个字符，再次检查。这个过程一直持续到找到所有字符串共有的前缀或者为空字符串。

4. 返回结果：最后返回找到的最长公共前缀。

方法一JavaScript版本代码如下：

function longestCommonPrefix(strs) {
  // 如果数组为空，直接返回空字符串
  if (strs.length === 0) return "";
  // 如果数组只有一个元素，返回该元素本身
  if (strs.length === 1) return strs[0];

  // 初始化最长公共前缀为第一个字符串
  let prefix = strs[0];

  // 遍历数组中的每个字符串，从第二个开始
  for (let i = 1; i < strs.length; i++) {
    // 当前字符串与前缀不匹配时，缩短当前前缀
    while (strs[i].indexOf(prefix) !== 0) {
      // 缩短前缀字符串
      prefix = prefix.substring(0, prefix.length - 1);
      // 如果前缀为空，说明没有公共前缀，返回空字符串
      if (prefix === "") return "";
    }
    // 当前字符串匹配前缀，继续检查下一个字符串
  }

  // 返回找到的最长公共前缀
  return prefix;
}

// 示例
console.log(longestCommonPrefix(["abca", "abc", "abca", "abc", "abcc"])); // "abc"
console.log(longestCommonPrefix(["abc"])); // "abc"

方法二：垂直扫描法

1. 初始化：同样检查输入数组是否为空，如果为空则直接返回空字符串。

2. 逐列比较：遍历第一个字符串的每个字符，将这些字符与其他字符串在相同位置的字符进行比较。

3. 构建公共前缀：如果在某个位置所有字符串的字符都相同，则将该字符添加到公共前缀中。如果在某个位置发现字符不匹配或某个字符串长度不足，则停止比较并返回当前的公共前缀。

4. 返回结果：最后返回构建好的最长公共前缀。

方法二JavaScript版本代码如下：

function longestCommonPrefix(strs) {
  // 如果数组为空，直接返回空字符串
  if (strs.length === 0) return "";

  // 初始化最长公共前缀为空字符串
  let prefix = "";

  // 遍历第一个字符串的每个字符
  for (let j = 0; j < strs[0].length; j++) {
    // 获取第一个字符串的当前字符
    const char = strs[0][j];
    // 遍历数组中的其他字符串
    for (let i = 1; i < strs.length; i++) {
      // 如果当前字符不在其他字符串的相同位置，或者当前字符串长度不足
      if (j >= strs[i].length || strs[i][j] !== char) {
        // 没有公共前缀，返回当前已找到的公共前缀
        return prefix;
      }
    }
    // 如果所有字符串在当前位置都有相同的字符，将该字符添加到公共前缀
    prefix += char;
  }

  // 返回找到的最长公共前缀
  return prefix;
}

// 示例
console.log(longestCommonPrefix(["abca", "abc", "abca", "abc", "abcc"])); // "abc"
console.log(longestCommonPrefix(["abc"])); // "abc"

相同测试用例方法一和方法二的运行效果对比如下图，可看出两个方法占用内存差不太多，但方法二的运行时间比方法一更高效一些。

总结与类似题解题思路

以上两个方法都实现了寻找字符串数组中最长公共前缀的功能。方法一通过逐个字符串进行水平扫描来缩短前缀，而方法二通过逐字符垂直扫描来构建前缀。两种方法都有其适用场景，但方法二在时间和空间复杂度上通常更优。

对于求解最长公共前缀这类问题，核心思路是逐步缩小问题的规模，直到找到所有字符串共有的前缀或者确定没有公共前缀为止。具体实现时，可以采用以下策略：

1. 初始化：总是先检查输入数组是否为空或只有一个元素，这些情况下可以直接返回相应结果。

2. 迭代或递归：通过迭代或递归的方式，逐步缩小问题的规模。在迭代中，可以通过缩短当前公共前缀（水平扫描法）或逐列比较字符（垂直扫描法）来实现。

3. 比较与更新：在每一步中，都需要比较当前公共前缀与新的字符串或字符，根据比较结果更新公共前缀。

4. 结束条件：当发现公共前缀为空或者已经比较到某个字符串的末尾时，就可以停止进一步的搜索，并返回当前的公共前缀。

对于类似的题目，比如求多个区间的交集、求多个数组的交集等，都可以采用类似的思路：逐步缩小问题的规模，通过比较和更新来找到共有部分，直到无法再找到共有部分为止。这种思路的关键在于找到合适的数据结构和方法来高效地进行比较和更新操作。