Find longest common prefix in strings Problem

Input: arr = {“apple”, “app”, “application”, “applause”};

Output: app

Explanation: The problem statement is quite simple to understand. The input contains a string array with multiple strings in it. The output is the longest common prefix which is present in the given strings.

One just has to check on the prefixes of each string. There are two approaches to solve it:

Case 1: Match every single word to check for the prefixes.
Case 2: Sort the set of strings to find the longest common prefix.

# Algorithm:

1. Pass the given array and its length to find the longest prefix in the given strings.
2. The function of finding the longest prefix, in turn, calls the function prefix to compare each word letter by letter for the prefix.
3. Return the prefix which is the longest and is common among all the strings.

Code:

#include<bits/stdc++.h> 
using namespace std; 
string pref(string s1, string s2) 
{ 
    string temp;
    int i,j;
    for (i=0, j=0; i<s1.length() && j<s2.length(); i++,j++) 
    { 
        if (s1[i] != s2[j]) 
        {
            break; 
        }
        temp.push_back(s1[i]); 
    } 
    return(temp); 
} 
string lf(string arr[], int len) 
{ 
    string p =  arr[0]; 
    int i; 
    for (i=1; i<len; i++) 
    {
        p = pref(p, arr[i]); 
    }
    return(p); 
} 
int main() 
{ 
    string a[] = {"apple", "app", "application", "applause"}; 
    int n = sizeof(a)/sizeof(a[0]); 
    string prefix = lf(a, n); 
    if (prefix.length()) 
    {
        cout<<"The longest common prefix is : "<<prefix;
    }
    else
    {
        cout<<"There is no common prefix";
    }
    return (0); 
}

Output:

The longest common prefix is : app

Time Complexity: O(N*M) where N is the number of strings and M is the length of the largest string.

 

# Optimized Algorithm

1. Pass the given array and its length to find the longest prefix in the given strings.
2. The function of finding the longest prefix sorts the array of strings.
3. It then assigns prefix length as the min value between the length of first and last string in the sorted array.
4. It iterates till the prefix length compares the characters to find the actual length of the prefix.
5. Finally, it stores the prefix value by obtaining from the substring of the string till the prefix length.
6. Return the prefix which is the longest and is common among all the strings.

Code:

#include<iostream> 
#include<algorithm> 
using namespace std; 
string lp(string arr[], int len) 
{
    sort(arr, arr + len);
    int preflen = min(arr[0].size(),arr[len - 1].size());
    string s1 = arr[0], sn = arr[len - 1]; 
    int i = 0; 
    while (i < preflen && s1[i] == sn[i]) 
    {
        i++; 
    }
    string p = s1.substr(0, i); 
    return p; 
} 
int main() 
{ 
    string a[] = {"apple", "app", "application", "applause"}; 
    int n = sizeof(a)/sizeof(a[0]); 
    string prefix;
    if (n==0)
    {
        prefix="";
    }
    else if(n==1)
    {
        prefix=a[0];
    }
    else
    {
        prefix=lp(a, n);   
    }
    cout << "The longest common prefix is: "<<prefix; 
    return 0; 
}

Output:

The longest common prefix is : app

Time Complexity: O(M*NlogN) where N is the number of strings and M is the max number of characters in any string.