14 最长公共前缀

题目

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

题解

1. 首先获取第一个字符串，遍历这个字符串依次跟数组里的其他字符串进行比较。

TIP

执行用时：84 ms, 在所有 JavaScript 提交中击败了 67.78% 的用户
内存消耗：38 MB, 在所有 JavaScript 提交中击败了 34.2% 的用户

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(!strs.length) return ''
  let set = [] // 公共前缀列表
  let count = strs[0].length  // 获取第一个长度，用来遍历
  let i=0

  while(i<count) {
    let str = '' // 当前字符串
    for(let j=0;j<strs.length;j++) {
       let item = strs[j]
       // str 存在，说明可以直接对比
       if(str) {
          if(str != item[i]) return set.join('') // 当遇到不一样的字符串时，则直接返回相同的前缀
        } else {
            // 如果不在，则需要初始化赋值
          str = item[i] 
        } 
    }

    set.push(str)
    i++
  }
  return set.join('')
};

• 时间复杂度： `O(mn)`，m 是平均字符串的长度，n 是字符串的数量
• 空间复杂度： `O(n)`，使用了一个额外空间来储存经过对比后的字符串
• 最好情况： 传入空字符串或者没有相同的公共前缀
• 最坏情况： 数组里的内容均为相同的公共前缀