经典题目

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例1:

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

示例2:

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

注意到 LCP 的计算满足结合律，有以下结论：

LCP(S1…Sn)=LCP(LCP(S1…Sk),LCP(Sk+1…Sn))

其中 LCP(S1…Sn) 是字符串 S1…Sn 的最长公共前缀，1 < k < n

基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀。对于问题 LCP(Si⋯Sj)，可以分解成两个子问题 LCP(Si …Smid) 与 LCP(Smid+1…Sj)，其中 mid=(i+j)/2 。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。

:::details 点击查看代码

function commonPrefix(lcpLeft,lcpRight){
    let minLen=Math.min(lcpLeft.length,lcpRight.length);
    for(let i=0;i<minLen;i++){
        if(lcpLeft.charAt(i)!=lcpRight.charAt(i)){
            return lcpLeft.substring(0,i);
        }
    }
    return lcpLeft.substring(0,minLen);
}
function divide(strArr,start,end){
    if(start==end){
        return strArr[start];
    }else{
        let middle=Math.floor((end-start)/2)+start;
        let lcpLeft=divide(strArr,start,middle);
        let lcpRight=divide(strArr,middle+1,end);
        return commonPrefix(lcpLeft,lcpRight);
    }
}
function longestCommonPrefix(strArr){
    if(!strArr||strArr.length==0){
        return '';
    }else{
        return divide(strArr,0,strArr.length-1);
    }
    
}

const strs = ["flower","flow","flight"];
console.log(longestCommonPrefix(strs));

:::

性能分析:

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。

空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 nlogn，每层需要 m 的空间存储返回结果。