# Longest common prefix

Posted on

Problem

I have made a function for finding the longest common prefix for the challenge on the leetcode site. This is the code:

``````var longestCommonPrefix = function(strs) {
let longestPrefix = '';
if (strs.length > 0) {
longestPrefix = strs;
for (let i = 1; i < strs.length; i++) {
for (let j = 0; j < longestPrefix.length; j++) {
if (strs[i][j] != longestPrefix[j]) {
longestPrefix = longestPrefix.slice(0, j);
break;
}
}
}
}

return longestPrefix;
};
``````

I am sure there is a way to make this code better, but not sure how to do that. Would appreciate any help.

Solution

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

``````var longestCommonPrefix = function(strs) {
if (!strs)
return '';

let smallest = strs.reduce( (min, str) => min < str ? min : str, strs );
let largest  = strs.reduce( (min, str) => min > str ? min : str, strs );

for (let i=0; i<smallest.length; i++) {
if (smallest[i] != largest[i])
return smallest.substr(0,i);
}

return '';
};
``````

In answer to `konijn` it would be minimally faster to get the smallest/largest by doing:

``````let smallest = strs;
let largest  = strs;
for (let i=1; i<strs.length; i++) {
let s= strs[i];
if (s > largest)  largest = s;
if (s < smallest) smallest = s;
}
``````

From a short review;

• You should sort the strings by length ascending if you start by assigning `longestPrefix = strs;` the prefix cannot be longer than the shortest string.
• I would assign `longestPrefix[j]` to a variable, avoiding an array access in a nested loop

• I would `return` the found value instead of calling `break`

• Break only exits one iteration in the loop anyway
• It seems okay that if no string list is provided, that `undefined` is returned
• Personal preference, I prefer `list` over `strs`

• `function(strs)` creates an anonymous function, which is terrible in stack traces, just use the good old `function longestCommonPrefix(strs) {`
• *