102 lines
3.4 KiB
JavaScript
102 lines
3.4 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/longest-common-prefix/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {string[]} strs
|
||
* @return {string}
|
||
*/
|
||
const longestCommonPrefix = function (strs) {
|
||
|
||
};
|
||
|
||
/*
|
||
如果字符串数组长度为0直接返回"",如果长度不为0则以字符数组中的第一个字符为公共前缀来比较，遍历整个字符数组，如果当前遍历到的字符
|
||
串包含整个公共前缀（第一个字符串）,如果不包含，就去掉当前公共前缀的末尾字符，继续比较，如果在比较的过程中发现公共前缀已经变成了
|
||
空字符就直接返回
|
||
*/
|
||
|
||
function f1(strs) {
|
||
if (strs.length === 0) return '';
|
||
let prefix = strs[0]; // 以字符数组中的第一个字符作为公共前缀
|
||
for (let i = 1; i < strs.length; i++) {
|
||
while (strs[i].indexOf(prefix) !== 0) { // 如果当前字符不包含公共前缀，说明公共前缀长了，要缩短
|
||
prefix = prefix.substring(0, prefix.length - 1); // 缩短前缀
|
||
if (prefix === '') return ''; // 没有公共前缀直接返回
|
||
}
|
||
}
|
||
return prefix;
|
||
}
|
||
|
||
/*
|
||
思路和上面的一致，先比较公共前缀的第一个字符，如果字符串数组的所有字符串都满足就比较公共前缀的第二个字符，如果发现比较的字符串
|
||
长度不够，或者当前字符不一致，直接返回公共前缀
|
||
*/
|
||
function f2(strs) {
|
||
if (strs.length === 0) return '';
|
||
|
||
for (let i = 0; i < strs[0].length; i++) {
|
||
const char = strs[0][i]; // 获取第一个字符串的当前字符
|
||
for (let j = 1; j < strs.length; j++) {
|
||
// 如果当前字符与其他字符串的对应位置字符不一致，返回当前公共前缀
|
||
if (i >= strs[j].length || strs[j][i] !== char) {
|
||
return strs[0].slice(0, i);
|
||
}
|
||
}
|
||
}
|
||
|
||
return strs[0]; // 如果循环结束，没有不匹配的，说明整个第一个字符串都是公共前缀
|
||
}
|
||
|
||
function f3(strs) {
|
||
if (strs.length === 0) return '';
|
||
|
||
let prefix = strs[0]; // 以第一个字符串作为初始公共前缀
|
||
|
||
for (let i = 1; i < strs.length; i++) {
|
||
let j = 0;
|
||
// 逐个字符比较当前公共前缀和下一个字符串
|
||
while (j < prefix.length && j < strs[i].length && prefix[j] === strs[i][j]) {
|
||
j++;
|
||
}
|
||
// 更新公共前缀为当前找到的前缀
|
||
prefix = prefix.slice(0, j);
|
||
|
||
// 如果公共前缀为空，直接返回
|
||
if (prefix === '') return '';
|
||
}
|
||
|
||
return prefix; // 返回最终的公共前缀
|
||
}
|
||
|
||
// 二分法代码
|
||
// TODO
|
||
function f4(strs) {
|
||
if (strs.length === 0) return ''; // 如果数组为空，直接返回空字符串
|
||
|
||
// 定义一个递归函数，用于计算区间 [start, end] 的最长公共前缀
|
||
function lcp(start, end) {
|
||
if (start === end) {
|
||
return strs[start]; // 如果区间只包含一个字符串，直接返回
|
||
}
|
||
|
||
// 计算中点，分成两半
|
||
const mid = Math.floor((start + end) / 2);
|
||
|
||
// 递归计算左右两部分的公共前缀
|
||
const lcpLeft = lcp(start, mid);
|
||
const lcpRight = lcp(mid + 1, end);
|
||
|
||
// 计算公共前缀的长度
|
||
const minLength = Math.min(lcpLeft.length, lcpRight.length);
|
||
|
||
// 比较两个公共前缀，找到它们的最长公共前缀
|
||
for (let i = 0; i < minLength; i++) {
|
||
if (lcpLeft[i] !== lcpRight[i]) {
|
||
return lcpLeft.slice(0, i); // 返回公共前缀
|
||
}
|
||
}
|
||
|
||
return lcpLeft.slice(0, minLength); // 返回较短的前缀
|
||
}
|
||
|
||
return lcp(0, strs.length - 1); // 对整个字符串数组进行递归处理
|
||
}
|