[Leetcode] Longest Common Prefix

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] consists of only lowercase English letters if it is non-empty.

how to approach?

horizontal scanning

function longestCommonPrefix(strs: string[]): string {
    if (strs.length === 0) return "";
    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        // console.log(strs[i])
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.slice(0, prefix.length - 1);
            // console.log('prefix', prefix)
            if (prefix === "") return "";
        }
    }

    return prefix;
}

1. when there is no element in strs, return empty string
2. set prefix as first element in strs array.
3. create for loop using strs element and inside the loop set while condition to check the prefix is included in the elements of strs array.
4. while prefix is not the part of the strs element, remove the character of prefix from the right side.
5. when prefix became empty string, return the empty string.
6. if prefix is left after for loop, return the prefix.

vertical scanning

function longestCommonPrefix(strs: string[]): string {
    if (strs == null || strs.length == 0) return "";
    
    for (let i = 0; i < strs[0].length; i++) {
        let c = strs[0][i];
        for (let j = 1; j < strs.length; j++) {
            if (i == strs[j].length || strs[j].charAt(i) != c){
                return strs[0].substring(0, i);
            }
        }
    }
    
    return strs[0];
}

1. if the strs is empty then return empty string.
2. in first for loop, it will cover the first item's whole characters
3. c varaible will be the each character of first element in strs.
4. second for loop, this will check all the other strings in the strs array.
5. when the element hits the length of i then it means its prefix can't be longer than that element, or the character at the i index is not same as the first element's i index character then it will have early return as substring of first element using i index.
6. if there was no early return then it means first element of strs itself is prefix.

divide and conquer

function longestCommonPrefix(strs: string[]): string {
    if (!strs || strs.length < 1) return "";

    let LCP = (str1: string, str2: string): string => {
        let minLen = Math.min(str1.length, str2.length);
        for (let i = 0; i < minLen; i++) {
            if (str1[i] !== str2[i]) {
                return str1.slice(0, i);
            }
        }
        return str1.slice(0, minLen);
    };

    let divideAndConquer = (strs: string[], l: number, r: number): string => {
        if (l === r) {
            return strs[l];
        } else {
            let mid = Math.floor((l + r) / 2);
            let lcpLeft = divideAndConquer(strs, l, mid);
            let lcpRight = divideAndConquer(strs, mid + 1, r);
            return LCP(lcpLeft, lcpRight);
        }
    };

    return divideAndConquer(strs, 0, strs.length - 1);
}

1. if the strs is null or strs has no length then return empty string.
2. set LCP function which get 2 str inputs and set the minLen between those 2.
3. set the for loop for those 2 and return the sliced string if there is mismatched character, if it's all matched under minLen then return the substring of minLen.
4. set divdeAndConquer which gets string array and the left, right index.
5. if left and right index is same then it means it only has one element in the array so return the element.
6. other than that case, create mid value which divides the strs in half.
7. and set the lcpLeft and lcpRight which happens recursively using divideAndConquer funciton. it has strs and the left index, mid index, right index.
8. and return the LCP of lcpLeft and lcpRight since LCP gets two strings as input.
9. lastly initialise the divideAndConquer which gets original strs array, 0 and the length of strs to make the recursive divideAndConquer happen.

Binary search

function longestCommonPrefix(strs: string[]): string {
    if (strs === null || strs.length === 0) return "";
    let minLen = Number.MAX_SAFE_INTEGER;
    for (let str of strs) minLen = Math.min(minLen, str.length);
    let low = 1;
    let high = minLen;
    while (low <= high) {
        let middle = Math.floor((low + high) / 2);
        if (isCommonPrefix(strs, middle)) low = middle + 1;
        else high = middle - 1;
    }
    return strs[0].substring(0, Math.floor((low + high) / 2));

    function isCommonPrefix(strs: string[], len: number) {
        let str1 = strs[0].substring(0, len);
        for (let i = 1; i < strs.length; i++)
            if (!strs[i].startsWith(str1)) return false;
        return true;
    }
}

1. when the strs is null or empty then return empty string
2. set minLent and use for loop to get the shortest length of the element.
3. set low and hight for length of common prefix, low will be 1 and hight will be the minimum length set above.
4. set while loop checking low and high value. set middle value by dividing sum of low and high and floor the value. and check the middle value with strs in is Common Prefix.
5. if it returned true then it means you don't need to check the first half since it has the common prefix at middle value so low will be middle + 1.
6. if it returned false then it means you don't need to check the second half since second half has different characters so it doesn't have common prefix and lower the gith as middle - 1.
7. when low value is bigger than high value then return the first element's substring using the middle value.
8. isCommonPrefix gets the strs array and the length to check the common prefix. and it return the boolean value to tell it has common prefix at the length or not.