题目

题目来源：力扣（LeetCode）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：

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

思路分析

纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

代码实现

  1. /**
  2.  * @param {string[]} strs
  3.  * @return {string}
  4.  */
  5. // 1. 纵向扫描
  6. // 时间复杂度：O(mn) m 表示字符串数组中所有字符串的平均长度，n 表示字符串数组的大小
  7. // 空间复杂度：O(1)
  8. var longestCommonPrefix = function (strs) {
  9.   if (strs.length == 0) return "";
  11.   const rows = strs.length;
  12.   const cols = strs[0].length;
  13.   //  先遍历 列，列就是每个字符
  14.   for (let i = 0; i < cols; i++) {
  15.     const firstChar = strs[0][i];
  16.     // 再遍历行，行就是每一个字符串
  17.     for (let j = 1; j < rows; j++) {
  18.       if (strs[j].length == i || strs[j][i] != firstChar) {
  19.         return strs[0].substr(0, i);
  20.       }
  21.     }
  22.   }
  23.   return strs[0];
  24. };

横向扫描

依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

代码实现

  1. // 2. 横向扫描
  2. // 时间复杂度：O(mn) m 表示字符串数组中所有字符串的平均长度，n 表示字符串数组的大小
  3. // 空间复杂度：O(1)
  4. var longestCommonPrefix2 = function (strs) {
  5.   if (strs.length == 0) return "";
  7.   let prefix = strs[0]
  8.   // 依次遍历每个字符串
  9.   for (let i = 1; i < strs.length; i++) {
  10.     // 比较两个字符串中的字符是否相等
  11.     prefix = longestCommonPrefixHelp(prefix, strs[i])
  12.     if (prefix.length == 0) return ""
  13.   }
  14.   return prefix
  15. };
  17. var longestCommonPrefixHelp = function (str1, str2) {
  18.   const len = Math.min(str1.length, str2.length)
  19.   let index = 0
  20.   while (index < len && str1[index] == str2[index]) {
  21.     index++
  22.   }
  23.   return str1.substr(0, index)
  24. }

参考阅读 https://leetcode-cn.com/problems/longest-common-prefix/solution/jian-dan-yi-dong-javac-pythonjs-zui-chan-jt6w/ https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/ https://leetcode-cn.com/problems/longest-common-prefix/solution/tu-jie-leetcodezui-chang-gong-gong-qian-zhui-lcp-b/