In the given input set of strings, write a program to find the longest common prefix.
Examples:
Input strings : {“code”, ”codex”, ”cosec”, ”coding”,”cobalt”}
Output : “co”
Time complexity : O(NM),
N = Number of strings
M = Length of longest string
Space complexity : O(M)
Algorithm
Here, instead of going through strings one by one, we will go through characters one by one.
1. We find the minimum length string from the input string array.
a. Traverse the string array.
b. Return length of minimum length string.
2. We traverse all the strings, and compare characters at same position.
3. If current character is same in all strings (same position) add it to result.
4. Return final result.
C++ Program
#include <bits/stdc++.h>
using namespace std;
//Function to find
//Length of minimum length string
int findMinLength(string string_array[], int n)
{
int min = string_array[0].length();
for (int i=1; i<n; i++)
{
if (string_array[i].length() < min)
{
min = string_array[i].length();
}
}
return(min);
}
string LCP(string string_array[], int n)
{
int minlen = findMinLength(string_array, n);
string output; //output string
char curr_char;
for (int i=0; i<minlen; i++)
{
//Compare all characters at same position in all strings
//If true append
curr_char = string_array[0][i];
for (int j=1 ; j<n; j++)
{
if (string_array[j][i] != curr_char)
{
return output;
}
}
//Append to output
output.push_back(curr_char);
}
return (output);
}
//Main function
int main()
{
string string_array[] = {"code","codex", "cosec", "coding","cobalt"};
int length = sizeof(string_array)/sizeof(string_array[0]);
string ans = LCP(string_array, length);
if(ans.length())
{
cout<<"Longest common prefix is: "<<ans;
}
else
{
cout<<"No common prefix found";
}
return 0;
}
){kind=link}