Longest Common Prefix

Description

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 "".

Solution

find the longest common prefix string amongst an array of strings

This part is a bit unclear to me.

Skimming through discussion lets me both know that I am not alone in finding the description a bit lacking and that the correct solution requires all strings in the array to share the prefix. Not just some of them.

Well… Let’s get at it.

If there is no common prefix, return an empty string "".

function longestCommonPrefix(strs) {
  let prefix = "";

  return prefix;
}

Boom. One out of the two given test cases are even passing. At this point you might think “Call it an MVP and wrap it?” but let me remind you that this is not work. We’re not getting paid for this, so obviously the answer is no. No quitting until we are bit shifting for no reason other than trying to look cool to the frontend developers.

Carrying on I’m going to let intuition drive this one and let my brain ride shotgun, as usual.

Because we know that any prefix we find must be common to all strings in strs we can simply pop the last string and use that as our baseline. It doesn’t really matter which string is used.

function longestCommonPrefix(strs) {
  let prefix = ""
+ const baseline = strs.pop()

  return prefix
};

I actually used shift() here initially but then my brain kicked in. pop() has the clear advantage of not having to reorder the entire array, thus reducing runtime.

Then plan is to loop through all characters of baseline and compare them to all characters of strs having the corresponding index which is simple enough.

function longestCommonPrefix(strs) {
  let prefix = "";
  const baseline = strs.pop();

  for (let i = 0; i < baseline.length; i++) {
    if (strs.some((str) => str[i] !== baseline[i])) {
      return prefix;
    }

    prefix += baseline[i];
  }

  return prefix;
}

Tests are passing and it doesn’t perform worse than average, so it’s good to go!

Happy coding!