2020-10-14 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀，返回空字符串""

题目分析

数组元素
最长公共前缀

参数说明

/**
 * @param {string[]} strs
 * @return {string}
 */

题解及实现

1. 纵向扫描

选择数组中第一个元素作为基准,从零开始,依此选择其字符,遍历数组除第一项外的元素,比较对应位置上的字符,若其余元素相应位置上的字符都相同,取下一位重复上述步骤,若有不同,返回之前保存的相同的位数

var longestCommonPrefix = function (strs) {
  if (!strs.length) return "";
  let i = 0;
  let result = "";
  while (strs[0][i]) {
    //防止第一项溢出
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== strs[0][i]) return result;
    }
    result += strs[0][i++];
  }
  return i ? strs[0] : ""; //如果第一个字符就不存在,返回"",如果是越界出的循环,返回完整的第一个item
};

时间复杂度:O(mn),数组中长度最小值和数组总长度的乘积

资源使用情况
- 执行用时：92 ms, 在所有 JavaScript 提交中击败了 59.26%的用户
- 内存消耗：40.7 MB, 在所有 JavaScript 提交中击败了 5.00%的用户
  常规思路

2. 横向扫描

先排除 strs.length 为 0 和 1 的情况,在数组长度为 2 以上时,先得出数组前两个元素的最长前缀,在此前缀不为零的前提下,迭代依此与数组剩余项得出最长前缀,若在迭代的过程中出现空字符串,直接返回,其余条件下,返回最后结果

//计算两个数的最长前缀
function twolongestPrefix(s1, s2) {
  if (!s1.length || !s2.length) return "";
  let length = s1.length > s2.length ? s2.length : s1.length;
  let i = 0;
  for (; i < length; ) {
    if (s1[i] === s2[i]) i++;
    else break;
  }
  return i ? s1.substring(0, i) : "";
}
//主函数,依此将数组元素放入上述函数迭代
var longestCommonPrefix = function (strs) {
  if (!strs.length) return "";
  if (strs.length === 1) return strs[0];
  //排除特殊情况
  let prefix = twolongestPrefix(strs[0], strs[1]);
  let i = 2;
  while (prefix && i < strs.length) {
    if ((prefix = twolongestPrefix(prefix, strs[i]))) i++;
    else return "";
  }
  return prefix;
};

时间复杂度:O(mn)

资源使用情况
- 执行用时：80 ms, 在所有 JavaScript 提交中击败了 91.47%的用户
- 内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了 31.68%的用户
  常规思路 2

3. 先sort再纵向扫描/横向扫描

基于事实：对于一组字符串的最长公共前缀长度不可能超过数组中长度最短的字符串的长度,所以我们可以先对数组中的item进行基于长度的排序,再在长度最小的item限制下,进行纵向扫描或者横向扫描

var longestCommonPrefix = function (strs) {
    if (!strs.length) return "";
    if (strs.length === 1) return strs[0];
    strs.sort((s1, s2) => {
        return s1.length - s2.length;
    })
    let i = 0;
    while(i<strs[0].length){
        for(let j = 1;j<strs.length;j++){
            if(strs[0][i]!==strs[j][i]) return strs[0].substring(0,i);
        }
        i++;
    }    
    return i ? strs[0].substring(0, i) : "";
};

资源使用情况
- 执行用时：88 ms, 在所有 JavaScript 提交中击败了73.08%的用户
- 内存消耗：39.3 MB, 在所有 JavaScript 提交中击败了16.98%的用户
  用时和sort函数内部实现有关