'Longest Common Prefix in Javascript

I am trying to solve the Leet Code challenge 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 lower-case English letters.

My solution:

let strs = ["flower", "flow", "flight"];

var longestCommonPrefix = function (strs) {
  for (let i = 0; i < strs.length; i++) {
    for (let j = 0; j < strs[i].length; j++) {
       // console.log(strs[i+2][j]);
      if (strs[i][j] == strs[i + 1][j] && strs[i + 1][j] ==strs[i + 2][j]) {
        return (strs[i][j]);
        
      } else {
        return "0";
      }
    }
  }
};

console.log(longestCommonPrefix(strs));

Output: f

How can I iterate over every character and check if it is same and then go for next and if it fails then the longest common prefix will be returned?

Solution 1:^[1]

As the longest common prefix must occur in every string of the array you can jus iterate over the length and check if all words have the same char at that index until you find a difference

function prefix(words){
  // check border cases size 1 array and empty first word)
  if (!words[0] || words.length ==  1) return words[0] || "";
  let i = 0;
  // while all words have the same character at position i, increment i
  while(words[0][i] && words.every(w => w[i] === words[0][i]))
    i++;
  
  // prefix is the substring from the beginning to the last successfully checked i
  return words[0].substr(0, i);
}

console.log(1, prefix([]));
console.log(2, prefix([""]));
console.log(3, prefix(["abc"]));
console.log(4, prefix(["abcdefgh", "abcde", "abe"]));
console.log(5, prefix(["abc", "abc", "abc"]));
console.log(6, prefix(["abc", "abcde", "xyz"]));

Solution 2:^[2]

Some of the issues:

Your inner loop will encounter a return on its first iteration. This means your loops will never repeat, and the return value will always be one character.
It is wrong to address strs[i+1] and strs[i+2] in your loop, as those indexes will go out of bounds (>= strs.length)

Instead of performing character by character comparison, you could use substring (prefix) comparison (in one operation): this may seem a waste, but as such comparison happens "below" JavaScript code, it is very fast (and as string size limit is 200 characters, this is fine).

The algorithm could start by selecting an existing string as prefix and then shorten it every time there is a string in the input that doesn't have it as prefix. At the end you will be left with the common prefix.

It is good to start with the shortest string as the initial prefix candidate, as the common prefix can certainly not be longer than that.

var longestCommonPrefix = function(strs) {
    let prefix = strs.reduce((acc, str) => str.length < acc.length ? str : acc);
    
    for (let str of strs) {
        while (str.slice(0, prefix.length) != prefix) {
            prefix = prefix.slice(0, -1);
        }
    }
    return prefix;
};

let res = longestCommonPrefix(["flower","flow","flight"]);

console.log(res);

Solution 3:^[3]

not the best solution but this should work

function longestPrefix(strs){
    if(strs.length <1){
        return "";
    }
    const sharedPrefix=function(str1,str2){
        let i=0;
        for(;i<Math.min(str1.length,str2.length) /*todo optimize*/;++i){
            if(str1[i] !== str2[i]){
                break;
            }
        }
        return str1.substr(0,i);
    };
    let curr = strs[0];
    for(let i=1;i<strs.length;++i){
        curr=sharedPrefix(curr,strs[i]);
        if(curr.length < 1){
            // no shared prefix
            return "";
        }
    }
    return curr;
}

Solution 4:^[4]

An approach based on sorting by word length, and for the shortest word, for exiting early, an entirely Array.every-based prefix-validation and -aggregation ...

function longestCommonPrefix(arr) {
  const charList = [];

  const [shortestWord, ...wordList] =
    // sort shallow copy by item `length` first.
    [...arr].sort((a, b) => a.length - b.length);

  shortestWord
    .split('')
    .every((char, idx) => {
      const isValidChar = wordList.every(word =>
        word.charAt(idx) === char
      );
      if (isValidChar) {
        charList.push(char);
      }
      return isValidChar;
    });

  return charList.join('');
}

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

.as-console-wrapper { min-height: 100%!important; top: 0; }

Solution 5:^[5]

this:

strs[i][j] == strs[i + 1][j] ==strs[i + 2][j]

makes no sense in JS... or at least, makes no sense in what you are doing... to do this you should use a && operator, like this:

strs[i][j] == strs[i + 1][j] && strs[i + 1][j] ==strs[i + 2][j]

Otherwise JS will evaluate the first condition, and then will evaluate the result of that operation (either true or false) with the third value

In addition to this, consider that you are looping with i over the array, and so i will also be str.length - 1 but in the condition you are referencing strs[i + 2][j] that will be in that case strs[str.length + 1][j] that in your case, makes no sense.

About the solution:
You should consider that the prefix is common to all the values in the array, so you can take in consideration one value, and just check if all the other are equals... the most obvious is the first one, and you will end up with something like this:

let strs = ["flower", "flow", "flight", "dix"];

function longestCommonPrefix (strs) {
  // loop over the characters of the first element
  for (let j = 0; j < strs[0].length; j++) {
    // ignore the first elements since is obvious that is equal to itself
    for (let i = 1; i < strs.length; i++) {
       /* in case you have like 
        [
          'banana',
          'bana'
        ]
        the longest prefix is the second element
       */
       if(j >= strs[i].length){
         return strs[i]
       }
       // different i-th element
       if(strs[0][j] != strs[i][j]){
         return strs[0].substr(0, j)
       }
       
    }
  }
  // all good, then the first element is common to all the other elements
  return strs[0]
};

console.log(longestCommonPrefix(strs));

Solution 6:^[6]

let strs = ["flower", "flow", "flight"];

var longestCommonPrefix = function (strs) {
  for (let i = 0; i < strs.length; i++) {
    for (let j = 0; j < strs[i].length; j++) {
        console.log(strs[i+2][j]);
      if (strs[i][j] == strs[i + 1][j] && strs[i][j]  ==strs[i + 2][j]) {
        return (strs[i][j]);
        


      } else {
        return "0";
      }
    }
  }
};

console.log(longestCommonPrefix(strs));

This **return ** f

Solution 7:^[7]

Increase the index while the letter is the same at that index for all words in the list. Then slice on it.

function prefix(words) {
  if (words.length === 0) { return '' }
  let index = 0;
  while (allSameAtIndex(words, index)) {
    index++;
  }
  return words[0].slice(0, index);
}

function allSameAtIndex(words, index) {
  let last;
  for (const word of words) {
    if (last !== undefined && word[index] !== last[index]) {
      return false;
    }
    last = word;
  }
  return true;
}

Solution 8:^[8]

I assume you are here for Leetcode problem solution.

var longestCommonPrefix = function(strs) {
let arr = strs.concat().sort();
const a1 = arr[0];
const a2 = arr[arr.length -1];
const length = a1.length;
let i=0;

while(i<length && a1.charAt(i) == a2.charAt(i)) i++;
return a1.substring(0,i);

};

Solution 9:^[9]

function prefixLen(s1, s2) {
    let i = 0;
    while (i <= s1.length && s1[i] === s2[i]) i++;
    return i;
}

function commonPrefix(arr) {
    let k = prefixLen(arr[0], arr[1]);
    for (let i = 2; i < arr.length; i++) {
        k = Math.min(k, prefixLen(arr[0], arr[i]));
    }
    return arr[0].slice(0, k);
}

console.log(commonPrefix(['pirate', 'pizza', 'pilates']))  // -> "pi"

Solution 10:^[10]

var longestCommonPrefix = function(strs) {
    let prefix = "";
    for(let i = 0; i < strs[0].length; i++) {
        for(let j = 1; j < strs.length; j++) {
            if(strs[j][i] !== strs[0][i]) return prefix;
        }
        prefix = prefix + strs[0][i];
    }
    return prefix;
};
console.log(longestCommonPrefix);

Solution 11:^[11]

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int main()
{
    char chr[50];
    printf("Enter string to get common letters :");
    gets(chr);
    char *token = strtok(chr, " ");
    char *arr[10];
    int i=0;
    while (token != NULL)
    {
        arr[i]=token;
        i++;
        token = strtok(NULL, " ");
    }
    char *var;
    int k=0,l=0;
    char temp, temp2;
    for(int j=0;j<=i;j++){
        var = arr[j];
        temp=var[k];
        var = arr[j+1];
        temp2=var[k];
        if(temp == temp2){
             if(i==j+2){
                j=-1;
                k++;
                printf("%c", temp);
                continue;
             }
             continue;
        }
    }
    return 0;
}

Solution 12:^[12]

It is as simple as one loop and compare each element of the strings

const longestPrefix = (strs) => {
[word1, word2, word3] = strs;
let prefix = [];
if(strs === null || strs.length <= 2 || strs.length > 3) return 'please 
insert 3 elements'

for (let i=0; i < word1.length; i++){ 
        if(word1[i] ===  word2[i] && word1[i] === word3[i]){
            prefix.push(word1[i])
        }
}
return prefix.join('')
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1
Solution 2
Solution 3	hanshenrik
Solution 4	Peter Seliger
Solution 5
Solution 6	AlexUnited
Solution 7
Solution 8	Tal
Solution 9	Tyler
Solution 10	Elikill58
Solution 11	Aman Pal
Solution 12	Xavier Guihot

'Longest Common Prefix in Javascript

Example 1:

Example 2:

Constraints:

My solution:

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]

Solution 7:[7]

Solution 8:[8]

Solution 9:[9]

Solution 10:[10]

Solution 11:[11]

Solution 12:[12]