5
\$\begingroup\$

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[0];
      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.

\$\endgroup\$
3
\$\begingroup\$

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[0] );
    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );

    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[0];
let largest  = strs[0];
for (let i=1; i<strs.length; i++) {
  let s= strs[i];
  if (s > largest)  largest = s;
  if (s < smallest) smallest = s;
}
\$\endgroup\$
  • \$\begingroup\$ Would a sort with a pop and an unshift not be faster? \$\endgroup\$ – konijn Dec 7 '17 at 18:40
  • 1
    \$\begingroup\$ fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition) \$\endgroup\$ – Marc Rohloff Dec 7 '17 at 22:34
  • \$\begingroup\$ How you you return an answer by inspecting only the shortest and longest? Consider {'ab', 'acd', 'abcd'} -> 'a' \$\endgroup\$ – Pierre Menard Dec 17 '18 at 19:57
  • \$\begingroup\$ Because if the smallest and largest string share a common prefix every other string would share it too. For example 'abaaa' and 'adeee' share the prefix 'a' everything inbetween ('abbbb', 'ac', 'ada', 'adaa') will all share the same prefix. \$\endgroup\$ – Marc Rohloff Dec 19 '18 at 15:17
2
\$\begingroup\$

From a short review;

  • You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; 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) {
  • *
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.