014.最长公共前缀

2021-04-25

题目

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

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

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

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

提示：

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、横向扫描法

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  if (strs.length === 0) {
    return "";
  }

  // 获取两个字符串的最长公共前缀
  const lcp = (str1, str2) => {
    const length = Math.min(str1.length, str2.length);
    let index = 0;
    while (index < length && str1[index] === str2[index]) {
      index++;
    }
    return str1.slice(0, index);
  };

  // 将第一个字符串设为默认前缀
  let prefix = strs[0];

  for (let i = 1; i < strs.length; i++) {
    prefix = lcp(prefix, strs[i]);
  }

  return prefix;
};