loading...

Leetcode - Longest Common Prefix (with JavaScript)

urfan profile image Urfan Guliyev ・2 min read

Today I am going to show how to solve the Leetcode Two Sum algorithm problem.

Here is the problem:
problem

These are the 2 most common solutions for this problem:

  1. Horizontal method - With this method we are taking the first and the second words from an array and comparing them letter by letter to see whether the beginning of each word is the exactly the same. Then, we take the common prefix and compare it one-by-one to the subsequent words in the array.
  2. Vertical method - With this method, instead of comparing two words at a time you, you compare all of the words at once, one letter at a time. I’m going to solve the problem with this method.

Both of these algorithms have exactly the same time and space complexity. But the vertical method is faster in solving the problem in the worst case scenario. Let’s just take a look at a really contrived example where you have an array of hundred words and all of the words are exactly the same except for the very last one. Using the horizontal method means that you have to make a comparison 99 times before you finally get down to the last word and realize that there is no common prefix. But with the vertical method all you need to do is go through the first letter of every single word and immediately realize that there is no common prefix.

var longestCommonPrefix = function(strs) {
    let prefix = ""
    if(strs === null || strs.length === 0) return prefix

    for (let i=0; i < strs[0].length; i++){ 
        const char = strs[0][i] // loop through all characters of the very first string. 

        for (let j = 1; j < strs.length; j++){ 
          // loop through all other strings in the array
            if(strs[j][i] !== char) return prefix
        }
        prefix = prefix + char
    }

    return prefix
}

Posted on by:

urfan profile

Urfan Guliyev

@urfan

Love coding, eating and travelling

Discussion

markdown guide