零 标题：算法（leetode，附思维导图 + 全部解法）300题之（14）最长公共前缀

导读：

一 题目描述

二 解法总览（思维导图）

三 全部解法

1 方案1

1)代码：

// 方案1 佛说：“有序胜过无序”
// 技巧：
// 1）将 strs 将一定顺序（升或降序）排列，
// 2）第1个和最后1个字符串的最长公共前缀就是我们的答案
var longestCommonPrefix = function(strs) {
    const l = strs.length;
    let index = 0,
        resStr = '';

    // 边界：若 strs的长度为 1，则直接返回 第1个字符串
    if (l === 1) {
        return strs[0];
    }

    // 1）将 strs 将一定顺序（升或降序）排列，
    strs.sort();

    // 边界：&& strs[0][index] !== undefined，是为了类似 ["", "", ""] 的情况
    // 2）第1个和最后1个字符串的最长公共前缀就是我们的答案
    while (strs[0][index] === strs[l - 1][index] && strs[0][index] !== undefined) {
        resStr += strs[0][index];
        index++;
    }

    return resStr;
};

2 方案2

1)代码：

// 方案2 不断遍历，借助"i、innerIndex"等变量去做处理。
var longestCommonPrefix = function(strs) {
    const l = strs.length;

    let innerIndex = 0,
        resStr = '';

    // 边界：若 strs的长度为 1，则直接返回 第1个字符串
    if (l === 1) {
        return strs[0];
    }

    // 1）不断遍历。
    // 核心：strs[0][innerIndex] === strs[i][innerIndex] ，即第1个（下标为0）字符串的某个字符（innerIndex）
    // === 第当前个（下标为i）字符串的某个字符（innerIndex）时，就不断往后走。
    // 注：当 i === l-1，”走完一轮了“，需要 innerIndex++; 且 i = 0（重置i）。
    // 边界：退出核心是 当 strs[0][innerIndex] !== strs[i][innerIndex] 时。
    for (let i = 1; i < l; i++) {
        // 边界：&& strs[0][innerIndex] !== undefined，是为了类似 ["", "", ""] 的情况
        if (strs[0][innerIndex] === strs[i][innerIndex] && strs[0][innerIndex] !== undefined) {
            if (i === l - 1) {
                innerIndex++;
                i = 0;
            }
            continue;
        } else {
            resStr = strs[0].slice(0, innerIndex);
            break;
        }
    }

    // 2）返回结果 resStr 。
    return resStr;
}

3 方案3

1)代码：

// 方案3 使用 Array.reduce 。
// 技巧：通过观察答案，我们发现 “输入到输出” 是一个多到一（字符串数组 变成 字符串）的过程，
// 故，我们可以优先考虑 Array.reduce 函数。
var longestCommonPrefix = function(strs) {
    // 1）使用 reduce（“多到一过程”） 进行遍历处理。
    const resStr = strs.reduce((acc, cur, index) => {
        if (index === 0) {
            acc = cur;
        } else {
            let index = 0,
                l = acc.length;
            while (index < l) {
                if (acc[index] === cur[index]) {
                    index++;
                } else {
                    break;
                }
            }
            acc = acc.slice(0, index);
        }
        return acc;
    }, '');

    // 2）返回结果 resStr 。
    return resStr;
}

4 方案4

1)代码：

// 方案4 “分治”。
// 核心：LCP(S1, S2, ..., Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn)) 。
var longestCommonPrefix = function(strs) {
    // 若分裂后的两个数组长度不为 1，则继续分裂
    // 直到分裂后的数组长度都为 1，
    // 然后比较获取最长公共前缀
    const lcp = (strs) => {
        const  l = strs.length;
        if(l === 1) {
            return strs[0];
        }

        const mid = Math.floor(l / 2),
            left = strs.slice(0, mid),
            right = strs.slice(mid, l);
        return lcpTwo(lcp(left), lcp(right))
    }

    // 求 str1 与 str2 的最长公共前缀
    function lcpTwo(str1, str2) {
        let index = 0,
            l = str1.length;

        while (index < l) {
            if (str1[index] === str2[index]) {
                index++;
            } else {
                break;
            }
        }

        return str1.slice(0, index);
    }

    const l = strs.length;
    if (l === 0) {
        return "";
    }

    return lcp(strs)
};