关于javascript:Leetcode-14-最长公共前缀

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

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

示例 1：

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

示例 2：

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

解题思路

第一种解法是一一比拟，先比拟第一和第二个字符串的最长公共前缀，而后再用这个前缀和第三个字符串比拟，以此类推。

function longestCommonPrefix(strs) {return strs.reduce((accu, cur) => {
    let prefix = "";
    for (let i = 0; i < accu.length; i++) {if (accu[i] === cur[i]) {prefix += accu[i];
      } else {return prefix;}
    }
    return prefix;
  })
}

应用 reduce 如果没有指定初始值，肯定要确保数组非空，因为这道题曾经阐明了 strs 长度大于等于 1，所以不必对空值进行解决

工夫复杂度：O(s)，s 是所有字符串中字符数量的总和
空间复杂度：O(1)

下面这种办法思路很容易想到，然而须要进行大量的遍历操作，工夫复杂度较高。第二种办法是仅比拟最大、最小字符串的最长公共前缀。这里说的最大、最小指的是 ACSII 编码的先后顺序，例如 ab 小于 abc，abc 小于 abcd，abcd 小于 ac，那么最小 ab 与最大 ac 的最长公共前缀肯定也是 abc 和 abcd 的公共前缀。

function longestCommonPrefix(strs) {
  let min = 0, max = 0;
  for (let i=0; i<strs.length; i++) {if (strs[min] > strs[i]) {
      // 记录最小字符串下标
      min = i;
    }
    if (strs[max] < strs[i]) {
      // 记录最大字符串下标
      max = i;
    }
  }
  for (let i=0; i<strs[min].length; i++) {if (strs[min].charAt(i) !== strs[max].charAt(i)) {return strs[min].substring(0, i);
    }
  }
  return strs[min];
}

工夫复杂度：O(n+m)，n 是数组的长度，m 是字符串数组中最短字符的长度
空间复杂度：O(1)