使用 JavaScript 解答 LeetCode 第 14 题,最长公共前缀,简单难度。

题目

原题链接

本题目是 LeetCode 题库第 14 题,由此访问。

题目描述

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

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

示例 1:

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

示例 2:

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

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

解题

AC 样例

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

  let res = [], i = 0;
  while (strs[0][i] && strs[strs.length-1][i]) {
    if(strs[0][i] == strs[strs.length-1][i]) res.push(strs[0][i]);
      else break;
    i++;
  }
  return res.join('');
};

解题思路

根据题目要求,明确边界条件的处理方式。如数组长度为 0 时,按要求返回 "";数组长度为 1 时,这个数据就是整个数组的最长公共前缀。

查找数组数据的最长公共前缀,理论上讲最长公共前缀长度是与数组中最短数据的长度相一致的,即最短数据本身就是整个数据的最长公共前缀。所以为缩减问题规模,将最短数据作为参照物进行比较即可。

将数组数据按 Unicode 点位排序,则最短字符串和最长字符串将分置在数组两端。若一个字符是最长公共前缀的一部分,则应在不同字符串的相应位置出现。所以以最短字符串长度为规模遍历其每一位的字符,并读取最长字符串中对应位置字符做比较,如同时存在且值相等,则该字符为数组最长公共前缀的一个字符。

最终将所有符合条件的字符合并为一个字符串作为答案返回即可。