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)
, whereS
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 stringS1
with the remaining strings[S2...Sn]
. There areS
character comparisons, whereS
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 theprefix
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