Leetcode: 14. Longest Common Prefix (Horizontal Scanning)

Finding the Longest Common Prefix Among an Array of Strings

Problem Statement

Given an array of strings strs, our task is to find the longest common prefix among all the strings. If there is no common prefix, we should return an empty string "".

For example:

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

In this case, the longest common prefix among the strings "flower," "flow," and "flight" is "fl".

Input: strs = ["dog","racecar","car"]
Output: ""

Here, there is no common prefix among the strings, so we return an empty string.

Solution Approach

To solve this problem, we can start by initializing our prefix variable with the first string in the array. Then, we iterate through the remaining strings, checking if the prefix is a prefix of each string. If it is not, we remove the last character from prefix and continue until either the prefix becomes empty or it becomes a prefix of the current string.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0)
        {
            return "";
        }
        string prefix = strs[0];
        for(int i = 1; i < strs.size(); i++)
        {
            while(strs[i].find(prefix) != 0)
            {
                prefix = prefix.substr(0, prefix.length() - 1);
            }
            if (prefix.empty())
                return "";
        }
        return prefix;
    }
};

Complexity Analysis

Let's analyze the time and space complexity of our solution:

• Time Complexity: The time complexity is O(S), where S is the sum of all characters in all strings. In the worst case scenario, where all the strings are the same, the algorithm compares the first string S1 with the remaining strings [S2...Sn]. There are S character comparisons, where S is the sum of all characters in the input array.
• Space Complexity: The space complexity is O(1) because we only use a constant amount of extra space to store the prefix variable and a few loop variables. We don't use any additional data structures that grow with the input size.

Example Scenarios

Let's go through a few example scenarios to understand the solution better.

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

We start with the initial prefix as "flower". We compare it with the remaining strings:

• Is "flower" a prefix of "flow"? No. We remove the last character from prefix, becoming "flow".
• Is "flow" a prefix of "flight"? Yes. We continue to the next string.

At this point, the longest common prefix is "fl".

Input: strs = ["dog","racecar","car"]

Here, there is no common prefix among the strings. The first string "dog" is our initial prefix, and it is not a prefix of the remaining strings. Thus, the result is an empty string.

Conclusion

In this blog post, we explored the problem of finding the longest common prefix among an array of strings. We provided an efficient solution in C++ and analyzed the time and space complexity. Understanding this problem and solution will help you find the longest common prefix in an array of strings effectively.