14. Longest Common Prefix

Longest Common Prefix 

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

 

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.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

For reference, the longest common prefix means the longest series of characters that are at the start of every string. For example, the longest common prefix in the words “had”, “hat” and “harp” is “ha”, whilst the longest common prefix in “only”, “one”, and “out” is “o”.

Approach 1) Double loop (BF)

In this solution, we initially loop through the first provided string’s characters. For each character,
we then loop through the remaining words, checking whether they contain the same character, in the same position.

If we find one that doesn’t, that means that the previous character tested marked the end of the longest prefix, so we return the first string up to and including that character. 

Otherwise, if our loops make it all the way to the end, that means the entire first string was found in all other strings, and thus that the entire first string is the longest prefix.
Let`s Code it!

var longestCommonPrefix = function (strs) {
    // Return early on empty input
    if (!strs.length) return '';

    // Loop through the letters of the first string
    for (let i = 0; i <= strs[0].length; i++) {
        // Loop through the other strings
        for (let j = 1; j < strs.length; j++) {
            // Check if this character is also present in the same position of each string
            if (strs[0][i] !== strs[j][i]) {
                // If not, return the string up to and including the previous character
                return strs[0].slice(0, i);
            }
        }
    }

    return strs[0];
};

Note:
I did originally use a combination of string1.indexOf(string2) === 0 and string1.substring(0, string2.length) === string2 for these comparisons, but then realised that comparing by 1 character each time made more sense, and was less CPU intensive.

Approach 2) Array.every()

Using the wonderful JavaScript array function every() (which returns whether or not every element in an array passes a given condition), we can remove the (visible) second loop and tidy up our code a little. 

But to be honest, it’s otherwise a near-identical solution (except for the fact that unlike with the double-loop approach, this one also checks the initial string, which is technically a pointless comparison as that’s where we started):

Let`s code it!

var longestCommonPrefix = function (strs) {
    // Return early on empty input
    if (!strs.length) return '';

    // Loop through the letters of the first word
    for (let i = 0; i <= strs[0].length; i++) {
        // Check if this character is present in the same position of every string
        if (!strs.every((string) => string[i] === strs[0][i])) {
            // If not, return the string up to and including the previous character
            return strs[0].slice(0, i);
        }
    }

    return strs[0];
};

Note: 

Although I used every(), you can also use some() with an inverted comparison to get the same result (in other words, “if some elements don’t contain this character” is the same as saying “if not every element contains this character”).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #14. Longest Common Prefix

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!