LeetCode 14 最长公共前缀

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

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


示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

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

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

解题思路

获取最长公共前缀，最简单的想法就是把strs中的每个字符串按照位置挨个进行比较，取strs中长度最小的字符串作为比较的基准，因为最大公共前缀最长也就是长度最小的那个字符串。然后挨个进行比较，如果发现不匹配的就将strs[0]切取0到当前匹配的位置，就是最长公共前缀。

var longestCommonPrefix = function(strs) {
    //获取strs中长度最小的字符串
    const minLength = Math.min(...strs.map((cell) => cell.length))
    let result = ''

    //循环遍历每一位的字符
    outer:for (let i = 0; i < minLength; i++) {
        const currentChar = strs[0][i]
        //将strs中其他的字符串都与strs[0]进行比较
        for (let j = 1; j < strs.length; j++) {
            if (currentChar !== strs[j][i]) { //不符合立即跳出循环
                result = strs[0].substring(0, i)  //截取对应长度的前缀
                break outer
            }
        }
    }
    return result
};

解题方式比较朴实无华，可以优化的点在于，每次都需要将strs[0]与strs中其他的字符串进行比较，如果我们将strs进行sort排序，默认的sort会进行字符串字符排序，导致偏差最大的两个字符串在首尾两处，这样就仅需要比较首尾字符串的不同。
如["flower","flow","flight"].sort()结束后结果是['flight', 'flow', 'flower']偏差最大的就是flight和flower了

var longestCommonPrefix = function (strs) {
  strs = strs.sort()
  for (let i = 0; i < strs[0].length; i++) {
    //比较首尾两处字符是否一样，如果不一样则返回最大公共前缀
    if (strs[0][i] !== strs[strs.length - 1][i]) {
      return strs[0].substring(0, i)
    }
  }
  //如果不是在循环中返回的话，说明是因为匹配完了字符串退出的循环，那么最大公共前缀就是strs[0]
  return strs[0]
}