Longest common prefix (Character by character)

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;
}
Try It

 


Next > < Prev
Scroll to Top