Longest Common Prefix

Wow💃, this is the seventh article in this interesting series and I think seven represents perfection.

I was afraid of starting this series and sharing my journey or what I am solving because of fear and what people will say but I remembered a quote by Roy T. Bennett

Do not fear failure but rather fear not trying. - Roy T. Bennett

In this article you will learn how to solve the Longest Common Prefix Question on Leetcode and I will solve the question in few steps below.

Let's get in✨

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

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution

Since we are getting the prefix from all the words and if it is not in at least a word we will return the common prefix, it means that we can use a word to check all other words.
Declare an empty string to store the longest common prefix.
```
// Longest Common Prefix
  let longestPrefix = "";
```
Let's use the first word in the array, we will loop through the first word and use every character of the first word to check every other word's character till we can't get any similar word again.
```
  // Length of First String
  let firstLength = strs[0].length;

  for (i = 0; i <= firstLength; i++) {
  }
```
Store every character of the first word in a variable called firstStringChar.

 let firstStringChar = strs[0].substring(0, i);

Check every character of the first word with other words and break the loop once there is a character that is not common to all words.
```
if (!strs.every(str => str.substring(0,i) == firstStringChar)) break;
```
After breaking the loop, the characters of the first word that we have iterated over to that point of breaking is the longest common prefix, so the firstStringChar now holds the longest common prefix.
Put the character that appears in all words in the longestPrefix which is the firstStringChar.
```
     longestPrefix = firstStringChar;
```
Finally, return the longest common prefix.

Compilation of the codes above.

// Length of First String
    let firstLength = strs[0].length;

    // Longest Common Prefix
    let longestPrefix = "";

    for (i = 0; i <= firstLength; i++) {
        let firstStringChar = strs[0].substring(0, i);

        if (!strs.every(str => str.substring(0,i) == firstStringChar)) break;
        longestPrefix = firstStringChar;
    }

      return longestPrefix;

The Time and Space Complexity

Time Complexity

This Solution has a Time complexity of O(n) which is a Linear time since we are looping through an array of strings and the time depends on the length of the array.

Space complexity

The Space Complexity is also O(1) since we don’t require any extra space, except the iterator, we can say that we require constant extra space, i.e irrespective of the size of an array, we require the same memory.

The Runtime is 76ms, faster than 82.43% of JavaScript online submissions for Longest Common Prefix and Memory Usage: 40.2 MB, less than 40.54% of JavaScript online submissions for Longest Common Prefix.

Longest Common Prefix Solution.JPG

Conclusion

I hope you have learnt a lot from this article and your contribution is also highly welcomed because we get better by learning from others, you can reach out to me on Twitter here. Watch out for more helpful contents on Data Structures and Algorithm from me.

Don't forget to Like, share and subscribe for more articles in this series called Solutions to Data Structures and Algorithm Questions on Leetcode.

Enjoy 🎉

Arimoro Olamilekan Ezekiel's Blog