算法题：14. 最长公共前缀

题

这题比较典型，虽然简单但是有挺多的优化空间。

解法一：纵向对比

思路

纵向对比。
遍历数组中第一个字符串，并依次对比数组中相同位置的字符。

代码

发现一年前的解答，就是用的纵向对比。

function longestCommonPrefix(strs: string[]): string {
    if(!strs.length)return "";
    let result = "";
     strs.sort((a,b)=>a.length - b.length);
    const first = strs[0];
    const other = strs.slice(1);
    for(let i = 0; i < first.length; i++){
        const char = first[i];
        if(other.every(it=>it[i]===char)){
            result += char;
        }else{
            return result;
        }
    }
    return result;
};

优化思路

现在看来有很多可以优化的空间，如：

1. 多余的sort，可以去掉
2. 字符串拼接不如最后截取字符串
3. 多余的slice，可以去掉
4. 去掉了slice，那么every也要去掉

优化后的代码

function longestCommonPrefix(strs: string[]): string {
    const len = strs.length;
    if(!len)return "";
    const first = strs[0];
    const firstLen = first.length;
    let char = '';
    for(let i = 0; i < firstLen; i++){
        char = first[i];
        for(let j = 1; j < len; j++){
            if(char !== strs[j][i]){
                return first.substring(0, i);
            }
        }
    }
    return first;
}

复杂度分析

• 时间复杂度：O(mn)O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

• 空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。

解法二：排序后头比尾

思路

根据群友答案反推：先数组排序，然后对比第一个和最后一个。

sort对字符串会优先对比每一个字符，那么数组中第一个和最后一个差异是最大的。

代码

function longestCommonPrefix(strs: string[]): string {
    const arrLen = strs.length;
    
    if(!arrLen) return '';
    if(arrLen === 1)  return strs[0];
    
    arrLen > 2 && strs.sort();
    const first = strs[0];
    const last = strs[arrLen - 1];
    const firstLen = first.length;
    let index = 0;
    for (let i = 0; i < firstLen; i++) {
        if(first[i] !== last[i]){
            break;
        }else {
            index++;
        }
    }
    return first.slice(0, index);
};

该解法依赖于sort函数，就像别人说的：

有点儿像是api的应用 不像是算法，就像 老师让你写排序，结果你直接调用sort

解法三：横向对比(公共递减对比)

思路

来自官方的解法：先取出数组中第一个字符串作为公共前缀，然后用它去逐一对比数组中其他字符串，寻找并更新公共前缀。
巧妙的是公共长度只会越来越短，需要遍历的次数会越来越少

代码

function longestCommonPrefix(strs: string[]): string {
    if(!strs.length) return '';
    let prefix = strs[0];
    const len = strs.length;
    for(let i = 1; i < len; i++){
        prefix = getPrefix(prefix, strs[i]);
        if (prefix.length == 0) {
            break;
        }
    }
    return prefix;
};

function getPrefix(prefix:string, s:string): string{
    let i = 0;
    const len = Math.min(prefix.length, s.length);
    while(i < len && prefix[i] === s[i]){
        i++;
    }
    return prefix.substring(0, i);
}

复杂度分析

• 时间复杂度：O(mn)O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。

解法四：纵向进阶-纵向加二分查找

在使用纵向查找的时候，是从左往右查起的，那么完全可以使用二分查找来代替，来减少查找次数。但是因为有可能中间字符一样，但前面字符不同，所以不能单个字符对比，必须连同前面的一起对比。

function longestCommonPrefix(strs: string[]): string {
    const len = strs.length;
    if(!len) return "";
    if(len === 1) return strs[0];
    const first = strs[0];
    let char = '';
    let left = 0; 
    let right = first.length; 
    let mid = 0; 

    while(left <= right){
        mid = ~~((right - left) / 2) + left;
        char = first.substring(0, mid);
        for(let j = 1; j < len; j++){
            if(char !== strs[j].substring(0, mid)){
                right = mid - 1;
                mid = left - 1;
                break;
            }
        }
        left = mid + 1;
    }

    return first.substring(0, mid);
};

解法五：分治

分治有点类似横向的二分查找，只是不会中断查找查找
原始数组['leetcode','leet','lee','le'] => 'le'图解:

function longestCommonPrefix(strs: string[]): string {
   if (strs == null || strs.length == 0) {
        return "";
    }
     return splitCommonPrefix(strs, 0, strs.length - 1);
};

function splitCommonPrefix(strs:string[], start:number, end:number){
     if (start == end) {
        return strs[start];
    } 
    const mid = ~~((end - start) / 2) + start;
    const lcpLeft = splitCommonPrefix(strs, start, mid);
    const lcpRight = splitCommonPrefix(strs, mid + 1, end);
    return commonPrefix(lcpLeft, lcpRight);
}

 function commonPrefix(lcpLeft:string, lcpRight:string) {
    const minLength = Math.min(lcpLeft.length, lcpRight.length);       
    for (let i = 0; i < minLength; i++) {
        if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
            return lcpLeft.substring(0, i);
        }
    }
    return lcpLeft.substring(0, minLength);
}

总结

sort方式太过于依赖sort了，普适性低，如果把字符串改为数组，用其他方式效率不变，但用sort方式效率则会非常低。