【算法篇】求最长公共前缀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”
解题思路

方法一：水平扫描法

• 初始化：首先检查输入数组是否为空，假如为空则直接返回空字符串。假如只有一个字符串，则返回该字符串自己，因为这时最长公共前缀就是这个字符串。
  
• 迭代比力：将第一个字符串作为初始的最长公共前缀。然后遍历数组中的其他字符串，对每个字符串使用indexOf方法检查当前公共前缀是否存在于该字符串中。
  
• 缩短当前公共前缀：假如发现当前公共前缀不在某个字符串中，就将公共前缀缩短一个字符，再次检查。这个过程不停连续到找到所有字符串共有的前缀大概为空字符串。
  
• 返回效果：最后返回找到的最长公共前缀。
  

方法一JavaScript版本代码如下：

1. function longestCommonPrefix(strs) {
2.   // 如果数组为空，直接返回空字符串
3.   if (strs.length === 0) return "";
4.   // 如果数组只有一个元素，返回该元素本身
5.   if (strs.length === 1) return strs[0];
7.   // 初始化最长公共前缀为第一个字符串
8.   let prefix = strs[0];
10.   // 遍历数组中的每个字符串，从第二个开始
11.   for (let i = 1; i < strs.length; i++) {
12.     // 当前字符串与前缀不匹配时，缩短当前前缀
13.     while (strs[i].indexOf(prefix) !== 0) {
14.       // 缩短前缀字符串
15.       prefix = prefix.substring(0, prefix.length - 1);
16.       // 如果前缀为空，说明没有公共前缀，返回空字符串
17.       if (prefix === "") return "";
18.     }
19.     // 当前字符串匹配前缀，继续检查下一个字符串
20.   }
22.   // 返回找到的最长公共前缀
23.   return prefix;
24. }
26. // 示例
27. console.log(longestCommonPrefix(["abca", "abc", "abca", "abc", "abcc"])); // "abc"
28. console.log(longestCommonPrefix(["abc"])); // "abc"

复制代码

方法二：垂直扫描法

• 初始化：同样检查输入数组是否为空，假如为空则直接返回空字符串。
  
• 逐列比力：遍历第一个字符串的每个字符，将这些字符与其他字符串在雷同位置的字符进行比力。
  
• 构建公共前缀：假如在某个位置所有字符串的字符都雷同，则将该字符添加到公共前缀中。假如在某个位置发现字符不匹配或某个字符串长度不敷，则停止比力并返回当前的公共前缀。
  
• 返回效果：最后返回构建好的最长公共前缀。
  

方法二JavaScript版本代码如下：

1. function longestCommonPrefix(strs) {
2.   // 如果数组为空，直接返回空字符串
3.   if (strs.length === 0) return "";
5.   // 初始化最长公共前缀为空字符串
6.   let prefix = "";
8.   // 遍历第一个字符串的每个字符
9.   for (let j = 0; j < strs[0].length; j++) {
10.     // 获取第一个字符串的当前字符
11.     const char = strs[0][j];
12.     // 遍历数组中的其他字符串
13.     for (let i = 1; i < strs.length; i++) {
14.       // 如果当前字符不在其他字符串的相同位置，或者当前字符串长度不足
15.       if (j >= strs[i].length || strs[i][j] !== char) {
16.         // 没有公共前缀，返回当前已找到的公共前缀
17.         return prefix;
18.       }
19.     }
20.     // 如果所有字符串在当前位置都有相同的字符，将该字符添加到公共前缀
21.     prefix += char;
22.   }
24.   // 返回找到的最长公共前缀
25.   return prefix;
26. }
28. // 示例
29. console.log(longestCommonPrefix(["abca", "abc", "abca", "abc", "abcc"])); // "abc"
30. console.log(longestCommonPrefix(["abc"])); // "abc"

复制代码

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

总结与类似题解题思路

以上两个方法都实现了探求字符串数组中最长公共前缀的功能。方法一通过逐个字符串进行水平扫描来缩短前缀，而方法二通过逐字符垂直扫描来构建前缀。两种方法都有其适用场景，但方法二在时间和空间复杂度上通常更优。
对于求解最长公共前缀这类问题，焦点思路是渐渐缩小问题的规模，直到找到所有字符串共有的前缀大概确定没有公共前缀为止。具体实现时，可以采用以下策略：

• 初始化：总是先检查输入数组是否为空或只有一个元素，这些环境下可以直接返回相应效果。
  
• 迭代或递归：通过迭代或递归的方式，渐渐缩小问题的规模。在迭代中，可以通过缩短当前公共前缀（水平扫描法）或逐列比力字符（垂直扫描法）来实现。
  
• 比力与更新：在每一步中，都需要比力当前公共前缀与新的字符串或字符，根据比力效果更新公共前缀。
  
• 结束条件：当发现公共前缀为空大概已经比力到某个字符串的末尾时，就可以停止进一步的搜索，并返回当前的公共前缀。
  

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。