Longest common prefix (word by word)


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, we use associate property

LCP(s1, s2, s3) = LCP(LCP(s1, s2), s3)

1.  We create a function to find common prefix for two strings.
a. Compare strings characters.
b. Push them to result, if same.
c. Return final result.

2. Make initial output_prefix as first element of input array.

3. Compare it to second it and store it in ouput_prefix and soon.

4. Return the final output_prefix.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
//function to find
//common prefix of two strings
string LCPUtil(string string1, string string2)
{
    string output;
    int length1 = string1.length(), length2 = string2.length();
    //Compare string1 and string2
    for (int i=0, j=0; (i<=length1-1) && (j<=length2-1); i++,j++)
    {
        if (string1[i] != string2[j])
        {
            break;
        }
        output.push_back(string1[i]); }
    return (output);
}
//Function to find LCP
//longest commmon prefix compare word by word 
string  LCP(string arr[], int n)
{
    string output_prefix =  arr[0];
    for (int i=1; i<=n-1; i++)
    {
        output_prefix = LCPUtil(output_prefix, arr[i]);
    }
    return (output_prefix);
}
 
 
//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;
}

Try It

 

Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup