### Leetcode: 14. Longest Common Prefix (Horizontal Scanning)

Finding the Longest Common Prefix Among an Array of Strings

# 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;
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.