跳到主内容

【算法题】最长公共前缀 - Javascript版本

上个月有个前端的同事进了字节,面试官问了一个问题,就是如何找出最长的公共前缀,于是针对这道题目做了一下记录,希望对你有所帮助。这道题目算是比较简单的一道题目。

题目

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

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

例子 1:

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

例子 2:

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

解题思路

递归实现

利用的知识点

  1. 获取最小字符串长度 minLen,减少比较数量
  2. 利用 substr 获取最小字符串的前 minLen 个字符
  3. 利用 arr.every 判断剩余的字符串是否全部包含在最小字符串中
  4. indexOf 判断最小字符串是否包含在剩余字符串中,如果存在返回 0,否则返回 -1
const longestCommonPrefix = function (strs) {
if (strs.length === 0) return "";
let str = "";
let minLen;
let minStr = strs[0];
strs.forEach((str) => {
minLen = minLen === undefined ? str.length : Math.min(str.length, minLen);
});
const findPrefix = (index) => {
const subStr = minStr.substr(0, index);
if (index > minLen) {
return;
}
if (strs.slice(1).every((str) => str.indexOf(subStr) === 0)) {
str = subStr;
findPrefix(index + 1);
} else {
return;
}
};
findPrefix(1);
return str;
};

使用循环实现

利用的知识点

  1. 字符串拆分成数组 str.split('')
  2. 利用 arr.every 判断每一个下标对应的字符是否相同
const longestCommonPrefix = function (strs) {
if (strs.length <= 1) return strs[0] || "";
const firstStr = strs[0].split("");
let str = "";
for (let j = 0; j < firstStr.length; j++) {
if (strs.slice(1).every((str) => str[j] === firstStr[j])) {
str += firstStr[j];
} else {
break;
}
}
return str;
};

leetcode 地址

最长公共前缀