LeetCode 14(Golang): Longest Common Prefix (Easy): String Traversal and Comparison Approach

Published in

Programmer’s Career

3 min readMay 5, 2024

Ever wondered how to find the longest common prefix string between an array of strings? Let’s explore two effective strategies to tackle LeetCode problem number 14, “Longest Common Prefix”.

Introduction

String manipulation is a key aspect of algorithmic problem-solving, day-to-day coding activities, and even many real-world software applications. A subclass of problems that falls into this category focuses on finding commonalities between different strings. This post will illuminate a particularly interesting example — the problem of establishing the “Longest Common Prefix” from an array of strings, which is problem number 14 on LeetCode.

Problem

This problem challenges us to find the longest common prefix string amongst an array of strings or return an empty string “” if no such prefix exists. For instance, given the input ["flower","flow","flight"], the longest common prefix is "fl". If there is no common prefix among the input strings, we return an empty string "". Link to the problem.

Solution

To efficiently solve this problem, we can adopt two slightly varied traversal and comparison approaches. The core idea behind these methods involves iterating over the characters of the strings in the array and comparing them from the start until they differ or one string ends.

Approach 1:

This approach first determines the minimum length across all strings. We then iterate over the characters of the strings up to the minimum length. During this, if we encounter a character at the same index in the strings that aren’t the same, we instantly return the common prefix up to that point.

Here’s the GoLang implementation:

Approach 2:

This method follows the same central logic as the previous one but uses a flag to decide when to break the loop instead of returning in the middle of the loop.

Here’s the GoLang code:

Time Complexity: Both solutions have a time complexity of O(n.m), where n represents the number of strings in the array, and m stands for the length of the longest string in the array. This is because, in the worst case, we could end up comparing m characters across n strings.

Space Complexity: The space complexity of both solutions is O(m), where m is the length of the common prefix. We use an additional array to store the common prefix, which, at maximum, could be as long as the shortest string in the array.

Analysis

Both solutions hinge on directly examining the strings. While they employ different methods for examining strings’ characters, both eventually compare each character of every string to find the common prefix. The first implementation returns the common prefix as soon as the same indexed characters cease to be equal, whereas the second uses a flag to control when to break out of the loop and construct the common prefix afterward.

Conclusion

Finding the longest common prefix among an array of strings can be efficiently handled by comparing characters at the same indices across all strings. While the problem may seem straightforward, it entails careful indexing and error handling, particularly when dealing with empty arrays or unequal string lengths.

Did you find the solution intriguing and helpful for your LeetCode journey? Let’s connect and learn together, stay tuned for similar problem analyses and add more tools to our coding toolbox.

Remember, practice makes perfect! So, keep practicing and happy coding!