Zero title: Leetode algorithm (with mind map + all solutions) 300 questions (14) the longest common prefix

Takeaway:

Title Description

An overview of binary solutions (Mind mapping)

Three total solution

Scheme 1

1) code:

// Buddha says, "Order is better than disorder."
/ / skills:
// 1) Order STRS in ascending or descending order,
// 2) The longest common prefix for the first and last strings is our answer
var longestCommonPrefix = function(strs) {
    const l = strs.length;
    let index = 0,
        resStr = ' ';
    
    // Boundary: if STRS has length 1, the first string is returned
    if (l === 1) {
        return strs[0];
    }

    // 1) Order STRS in ascending or descending order,
    strs.sort();

    // boundary: &&strs [0][index]! == undefined for situations like ["", "", ""]
    // 2) The longest common prefix for the first and last strings is our answer
    while (strs[0][index] === strs[l - 1][index] && strs[0][index] ! = =undefined) {
        resStr += strs[0][index];
        index++;
    }

    return resStr;
};
Copy the code

Scheme 2

1) code:

// Plan 2 iterates through, using variables such as "I" and innerIndex.
var longestCommonPrefix = function(strs) {
    const l = strs.length;

    let innerIndex = 0,
        resStr = ' ';

    // Boundary: if STRS has length 1, the first string is returned
    if (l === 1) {
        return strs[0];
    }

    // 1) keep iterating.
    STRS [0][innerIndex] === STRS [I][innerIndex] === STRS [I][innerIndex]
    // === = a character (innerIndex) in the first string (subscript I).
    // innerIndex++ is required when I === l-1, "completed round"; And I = 0 (reset I).
    // Boundary: Exit core when STRS [0][innerIndex]! = = STRS [I] [innerIndex].
    for (let i = 1; i < l; i++) {
        // Boundary: &&strs [0][innerIndex]! == undefined for situations like ["", "", ""]
        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) return the result resStr.
    return resStr;
}
Copy the code

3 solution 3

1) code:

// Scheme 3 uses array.reduce.
// Tip: By looking at the answer, we see that input to output is a many-to-one process,
// Therefore, we can give preference to the array.reduce function.
var longestCommonPrefix = function(strs) {
    // 1) Use reduce (" more than one process ") for traversal processing.
    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) return the result resStr.
    return resStr;
}
Copy the code

4 scheme 4

1) code:

// Divide and conquer.
// core: LCP(S1, S2... , Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn)).
var longestCommonPrefix = function(strs) {
    // If the length of the two arrays is not 1, continue to split
    // Until the array is split, the length is 1.
    // Then compare to get the longest public prefix
    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))
    }

    // find the longest common prefix str1 and 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)
};
Copy the code