最长公共前缀

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

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

示例 1:

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

示例 2:

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

// 没有看题解前
// 执行用时：80 ms, 在所有 JavaScript 提交中击败了 71.96% 的用户
// 内存消耗：37.9 MB, 在所有 JavaScript 提交中击败了 86.95% 的用户
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  let res = strs[0]
  for (let i = 1; i < strs.length; i++) {
    const ss = strs[i]
    if (ss.startsWith(res)) continue
    else {
      for (let j = res.length - 1; j >= 0; j--) {
        if (ss.startsWith(res.substring(0, j))) {
          res = res.substring(0, j)
          break
        }

        if (j === 0) res = ''
      }
    }
  }
  return res || ''
}

官方题解

// 横向扫描
// 执行耗时什么都是一样的
// 看完题解后稍微改动
// 还有很多方法，比如分治，二分，竖向扫描
var longestCommonPrefix2 = function (strs) {
  let res = strs.sort((a, b) => a.length > b.length)[0]
  for (let i = 1; i < strs.length; i++) {
    const ss = strs[i]
    if (ss.startsWith(res)) continue
    else {
      for (let j = res.length - 1; j >= 0; j--) {
        if (ss.startsWith(res.substring(0, j))) {
          res = res.substring(0, j)
          break
        }

        if (j === 0) res = ''
      }
    }
  }
  return res || ''
}