loading...
Cover image for Finding the Longest Common Prefix

Finding the Longest Common Prefix

alisabaj profile image Alisa Bajramovic ・5 min read

Algorithm of the Day (35 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 33 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript

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!

Algorithm of the Day (35 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 33 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript

Posted on Jun 3 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

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;
};