LeetCode Series: Longest Common Prefix

The Problem:

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"

The Solution:

This is a question from leetcode. Let me show you the solution and try to explain my approach. In Data Structures and Algorithms this type of problems are known as sliding window problems. If you take a closer look at the example you see the longest common prefix will always be present in the shortest string so, that’s our first step to get the shortest string from the array. In order to calculate shortestString we use reduce function instead of while loop or Math.min approach as reduce approach is faster. What we are doing inside reduce is basically comparing the length of curr item with the previous item and if the length is less than what is in the acc we return the item else acc. Then we run a loop from last of the string get the prefix and compare it with each array element again using reduce. But, make sure to put that longestPrefix.length check otherwise you will end up with a random common prefix. And finally we return the prefix. For single element strings we simply return the only element at the top.

The Steps:

• Check if array of string is of length 1. If yes return 0th element of the array
• Now to keep the function pure assign strs to new variable arr which we will later modify.
• Now get the shortest string by using reduce method
• Store the length of shortestString in our counter.
• Now filter the arr to exclude the shortestString element for optimisation
• Now run the while loop
• Get the prefix, compare the prefix again with reduce method and not forgetting longestPrefix.length condition
• Finally updating counter and once loop is done return longestPrefix.
• Also Find the video for this question here.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length == 1){
        return strs[0];
    }
    let arr = strs;
    let shortestString = arr.reduce((acc,item) => acc.length > item.length ? item : acc, arr[0]);
    let i = shortestString.length;
    arr = arr.filter(item => item!==shortestString);
    let longestPrefix = '';
    while(i>0){
        let prefix = shortestString.substring(0,i);
        if(arr.reduce((acc, item) => (acc && item.substring(0,i) == prefix),true) && longestPrefix.length < prefix.length){
            longestPrefix = prefix;
        }
        i--;
    }
    return longestPrefix;
};