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

## Comments

## Post a Comment