Find the longest common prefix

Given an array of strings we have to find the longest common prefix between them. If there is no prefix then return empty string.

Example

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

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

Method 1: Using sorting to find the longest common prefix.

The idea is to.

• Sort the strings in ascending order based on their length.
• Then use the smallest among them and iterate for each character for it, because max prefix will be less than or equal to the smallest string.
• In each iteration check if prefix exists for the remaining words or not, if it exists then store it, else break and return the string.

const longestCommonPrefix = (strs) => {
    //If empty array return empty string
    if(strs.length === 0){
        return "";
    }
    
    //To track the prefix
    let lc = "";
    
    //Sort the string in ascending order
    strs.sort((a, b) => ('' + a).localeCompare(b));
    
    //Get the smallest string.
    let smallest = strs[0];
   
    //so that we have to iterate for it only.
    for(let i = 0; i < smallest.length; i++){
          //Get the first letter
          let current = smallest[i];
         
          //Flag to check if prefix is present in the remaining string
          let isPresent = true;
          
         for(let values of strs){
            //Break if different letter
            if(values[i] !== current){
               isPresent = false;
               break;
            }
         }
         
         //Break the loop if no prefix
         if(i === 0 && !isPresent){
             break;
         }
         
         //Add the prefix
         lc += isPresent ? current : ''; 
    }
    
   //return the prefix
   return lc;
};

Input:
console.log(longestCommonPrefix(["flower","flow","flight"]));

Output:
"f1"

Time complexity: O(nlogn + (n * length of smallest word in the string)).
Space complexity: O(1) or O(n) if we are using different sort.

---

Method 2: By deleting the characters from end.

Conceptually this is how it works.

• Get the first word from the array.
• Iterate for each word in the array and check if it is not the same word.
• Then keep on removing the characters from the end till the prefix is found.
• If there is no prefix and string becomes empty then break and return empty string.

const longestCommonPrefix = (strs) => {
    //If empty array
    if(strs.length == 0) {
        return "";
    }
    
    //Get the first word
    let str = strs[0];
    
    //look for prefix in each word
    for (const word of strs) {
        while (word.indexOf(str) !== 0) {
            // remove one character from the end
            str = str.substring(0, str.length - 1);
            if (str === ""){
                break;
            }
        }
    }
    return str;
};

Time complexity: O(n * length of the largest string).
Space complexity: O(1).