14. Longest common prefix

The title

Write a function to find the longest public prefix in an array of strings. Returns the empty string “” if no public prefix exists. Example 1: * *

Input:"flower"."flow"."flight"] output:"fl"Input:"dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix.Copy the code

Train of thought

horizontal

Horizontal scanning here refers to scanning each column of characters from back to front.

/** * @param {string[]} strs * @return {string} */
var longestCommonPrefix = function(strs) {
    // Handle the boundary case first
    if(! strs || ! strs.length || !Array.isArray(strs)) return ' '
    // Defaults to the first as the longest public prefix
    let prefix = strs[0]
    for (let i = 1; i < strs.length; i++) {
        // Keep looking for the longest public prefix ([prefix])
        const curStr = strs[i]
        while(curStr.indexOf(prefix) ! = =0) {
            prefix = prefix.substring(0, prefix.length - 1)
            if(! prefix)return ' '}}return prefix
};
Copy the code

Time complexity: O(S), where S is the sum of each character in STRS. Space complexity: O(1).

Advanced horizontal scanning

One problem with the previous algorithm is that if the array defaults to the shortest string s, it scans all characters before s.

So our optimization strategy is to scan each column of the string backwards instead.

/** * @param {string[]} strs * @return {string} */
var longestCommonPrefix = function(strs) {
    // Handle the boundary case first
    if(! strs || ! strs.length || !Array.isArray(strs)) return ' '
    const start = strs[0]
    for (let i = 0; i < start.length; i++) {
        const char = start[i]
        for (let j = 1; j < strs.length; j++) {
            I === STRS [j]. Length can skip unnecessary character comparisons
            // Then compare the characters at the same position in each string
            if(i === strs[j].length || char ! == strs[j][i]) {return start.substring(0, i)
            }
        }
    }
    // By default, the first is the shortest, i.e. the longest, public prefix
    return start
};
Copy the code

Time complexity: O(S). The worst-case time complexity is n strings of length m, and then we do nm comparisons, because we’re comparing each character. But the best-case time complexity is nmin(m), depending on the shortest length of the string. Space complexity: O(1).

Divide and conquer

/** * @param {string[]} strs * @return {string} */
var longestCommonPrefix = function(strs) {
    // Handle the boundary case first
    if(! strs || ! strs.length || !Array.isArray(strs)) return ' '
    return splitLongestPrefix(strs, 0, strs.length- 1)

    function splitLongestPrefix(strs, left, right) {
        // Stop recursion if left and right Pointers are equal
        if (left === right) {
            return strs[left]
        }
        const mid = Math.floor((left+right)/2)
        const leftStr = splitLongestPrefix(strs, left, mid)
        const rightStr = splitLongestPrefix(strs, mid + 1, right)
        // Make a pairwise comparison
        return commonPrefix(leftStr, rightStr)
    }
    function commonPrefix(leftStr, rightStr) {
        // Pairwise compare individual characters by the same index position
        // Select base with the shortest length
        const minLength = Math.min(leftStr.length, rightStr.length)
        for (let i = 0; i < minLength; i++) {
            if(leftStr[i] ! == rightStr[i]) {return leftStr.substring(0, i)
            }
        }
        return leftStr.substring(0, minLength)
    }
};
Copy the code

Worst case: n identical strings of length m time complexity O(S), S= MN. Space complexity O(mlogn).

Binary search method

/** * @param {string[]} strs * @return {string} */
var longestCommonPrefix = function(strs) {
    // Handle the boundary case first
    if(! strs || ! strs.length || !Array.isArray(strs)) return ' '
    // Find the shortest string in STRS, which is potentially the longest string possible
    let minStrLen = Number.MAX_SAFE_INTEGER;
    strs.map(str= > {
        minStrLen = Math.min(minStrLen, str.length)
    })
    // Binary search for the longest possible string
    let left = 1
    let right = minStrLen
    // Note the dichotomy termination condition
    while(left <= right) {
        let mid = Math.floor((left+right)/2)
        if (isStartWithCommonStr(strs, mid)) {
            left = mid + 1
        } else {
            right = mid - 1}}function isStartWithCommonStr(strs, mid) {
        let commonStr = strs[0].substring(0, mid)
        for (let i = 1; i < strs.length; i++) {
            if(! strs[i].startsWith(commonStr)) {return false}}return true
    }
    return strs[0].substring(0.Math.floor((left+right)/2))};Copy the code

The worst case is Slogn (Slogn). Time complexity O(Logn) is the number of binary iterations. S = MN. Space complexity O(1).

advertising

If you think it’s interesting, click on the lower right corner, or pay attention to it directly.