Longest Common Prefix using cpp
Asked 1 year ago
0Comments
0 Views
Imagine you have a bunch of words, and you want to find the part at the beginning that's the same for all of them. That's what this code does! Here's how it works:
First, we check if we have any words at all. If not, we say there's no common part.
Let's say we have these words: ["flower", "flow", "flight"]
We start looking at these two words, letter by letter, from the beginning:
- If the letters match, we add that letter to our answer.
- If they don't match, we stop and give the answer we have so far.
We keep doing this until we run out of letters in either word.
The Code for this Approch Looks Like this !
string longestCommonPrefix(vector<string>& strings){
string answer = "";
int i = 0 ;
while(true){
char curr_ch = 0 ;
// for each loop
for (auto str: strings){
if (i > = str.size()){
// out of bound
curr_ch = 0;
break ;
}
if (curr_ch == 0)
{
curr_ch = str[i]; //first string (april) (a)
}
else if (str[i] != curr_ch ) // means
{
curr_ch = 0 ;
break;
}
}
if (curr_ch == 0)
{
break ;
}
answer.push_back(curr_ch);
i++;
}
return answer ;
}
int main() {
vector<string> strings = {"appil", "ap", "apple"};
string answer = longestCommonPrefix(strings);
cout << "Longest Common Prefix is: " << answer << endl;
return 0;
}
Second Approch !
This method is smart because:
- Sorting helps us find the most different words quickly.
- We only need to compare two words instead of all of them.
- We stop as soon as we find a difference, saving time.
Let's say we have these words: ["flower", "flow", "flight"]
After sorting: ["flight", "flow", "flower"]
We compare "flight" and "flower":
f l i g h t
f l o w e r
↑
They match, so we add 'f' to our answer.
f l i g h t
f l o w e r
↑
They match, so we add 'l' to our answer.
f l i g h t
f l o w e r
↑
They don't match, so we stop here.and the Code Excecution looks like this :
string longestCommonPrefix(vector<string>& strs) {
string ans = "";
if (strs.empty()) {
return ans; // Return empty string if input vector is empty
}
// Sort the vector lexicographically
sort(strs.begin(), strs.end());
// First and last string after sorting
string first = strs[0];
string last = strs[strs.size() - 1];
// Compare characters of first and last string
for (int i = 0; i < first.size() && i < last.size(); i++) {
if (first[i] != last[i]) {
return ans;
}
ans += first[i];
}
return ans;
}- This method may be faster for larger datasets, as comparing only two strings is generally quicker than comparing all strings simultaneously.
- However, the sorting step adds some overhead, which might not be worth it for small datasets.
This method modifies the input vector (by sorting it), which might not be desirable in some cases.
Both approaches are valid and have their own advantages.
Give it a try in LEETCODE
https://leetcode.com/problems/longest-common-prefix/
Share