Finding the Longest Common Prefix

Today's algorithm of the day is the Longest Common Prefix Problem:

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

For example, if you're given the strings "stark", "stand", and "stew", your function should return "st", since that's the longest prefix shared by all of the words.

I like this problem because there's so many different ways to go about solving it. In this post, I'll go over just one method, explaining my approach and walking through the code in JavaScript.

The Approach

I'm going to approach this solution by thinking about what it means to have a common prefix. If you take the word "apply" and compare it to "apples", you can see that they share most of their letters--"appl". To get to that point of a shared start, you can remove the letters, one at a time, from the end of one of the words.

Let's take "apply" as the word we'll be removing letters from, comparing it against "apples". The whole word "apply" is not found in "apples", so let's remove the last letter from "apply". Now we have "appl". The string "appl" is found in "apples"--in fact, it starts at index 0--as in, the string "appl" is at the very start of "apples", and therefore it's the common prefix of "apply" and "apples".

We're going to use that logic to approach this problem: take the first word, then remove letters from the end of it, until it matches the start of the subsequent words.

The Code

It's often good to start writing out algorithm solutions by thinking of base cases. In this problem, one base case is that the given array, strs, is empty. If that's the case, then there's no way there can be a shared prefix, since there are no strings at all, so we can return an empty string.

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  //...
}

Now, just like in the case of "apply" and "apples", we'll want to have one word that we're comparing the others against. We could get the shortest word in the inputted array (since that would save some time), or we could just get the first word in the inputted array.

In this solution, I'll just choose the first word in the inputted array, which can be found with strs[0], and I'll set it equal to a new variable, prefix. This variable will be modified in the function, but it ultimately is what I'll want to return at the end, so I can include a return statement at the bottom of the function.

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  //...
  return prefix;
}

Now is when we'll compare the other strings. To do this, we can use a for loop, going from the second word in the inputted array (index 1), until the end of the array (strs.length). We'll want to check every word in strs.

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

If the start of each word is not the current prefix, then we know we need to modify the prefix. One way to check the start of each word is by using the indexOf() method for strings. indexOf() returns the index of the first occurrence of the passed in value. If the value is not found, it'll return -1. For example:

const word = "sunset"
const searchTerm = "set"

console.log(word.indexOf(searchTerm)) // output: 3

Index 3 is where the searchTerm first appears in the word. In another example:

const word = "sunset"
const searchTerm = "xyz"

console.log(word.indexOf(searchTerm)) // output: -1

-1 is returned because the searchTerm is not found in the word.

You can find more information about indexOf in the MDN documentation here.

For this problem, we're only interested in instances when indexOf would return 0, because that's the start of the word, and therefore the prefix. Therefore, as long as indexOf does not return 0, we'll want to do something to the working prefix. This is a good time to use a while loop.

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      //...
    }
  }
  return prefix;
}

Inside the while loop, we know that the current prefix is not found at the start of the current word we're checking. That means that we should remove the last letter of the prefix, and then check again. There's a few ways to remove the last letter of a string--one of which is .slice(). The .slice() method takes a section of a string, based on the passed in indexes, and returns it as a new string. (You can learn more about .slice() from the MDN docs here.)

Because we'll want to keep all of the original prefix, except for the last letter, we can slice from 0 to prefix.length-1 (note that the character at the end index is not included in a slice). We can then set this equal to prefix.

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, prefix.length - 1);
    }
  }
  return prefix;
}

Since we have a while loop that's set to continue going as long as the prefix is not found at the start of the current word, we're done with the function! It'll return a common prefix, or, if there is no common prefix, the while loop will continue slicing the prefix until there's nothing remaining. Note: when using indexOf, an empty string will be considered at the 0th index, so if there is no common prefix, then the empty string will be returned.

Because the while loop is wrapped in a for loop, after checking the word at index 1, and modifying the prefix as needed, it'll move onto the word at index 2, and so on. At each word, either the prefix is already found at the 0th index of the current word, or the while loop will shorten the prefix until it matches the start of the current word.

--

Let me know if you've got any questions or ideas for how to approach this problem!

Comments

[Saloni Yadav]

a slight alternative. Not sure whether the approaches have a different time complexity or not. You could help me with that?

var longestCommonPrefix = function(strs) {
    if(strs.length==0)
        return "";
    let pre = strs[0];
    var newpre = '';
    for (s of strs) {
        newpre='';
        for (let i=0; i<Math.min(s.length, pre.length); i++) {
            if (s[i]==pre[i]) {
                newpre+=s[i];
            } else {
                break;
            }
        }
        pre = newpre;
    }
    return newpre;
};