Longest Common Prefix of a String

Arunima Mandal

Brute-Force (Vertical Scanning):

Here we are returning an empty string if no common prefix is found.

Time Complexity: O(S) where S is the sum of all characters present in the vector. Or we can say O(mn) where m is the length of the vector and n is the length of the strings (assuming of highest limit) inside the vector.

Space Complexity: O(1) as constant space for the answer only.

#include <bits/stdc++.h>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    string ans="";
    for(int j=0; j<strs[0].size(); j++)
    {
        char ch=strs[0][j];
        for(int i=1; i<strs.size(); i++)
        {
            if(j>=strs[i].size() || strs[i][j]!=ch)
            {
                return ans;
            }
        }
        ans+=ch;
    }
    return ans;
}

int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Binary Search:

The trick to using the binary search in this problem is to find out the minimum length string first, and then apply binary search to it.

Time Complexity: O(S*log(n)) where S is the sum of all characters in the vector and n is the size of the length of the minimum string.

Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isCommonPrefix(vector<string>& strs, int len)
{
    string s=strs[0].substr(0,len);
    for(int i=1; i<strs.size(); i++)
    {
        if(strs[i].substr(0,len)!=s) return false;
    }
    return true;
}

string longestCommonPrefix(vector<string>& strs) {
    string mini_str;
    int mini=300;
    for(int i=0; i<strs.size(); i++)
    {
        if(strs[i].size()<mini)
        {
            mini=strs[i].size();
            mini_str=strs[i];
        }
    }
    if(mini==0) return "";

    int low=1; //Can't initialize it to 0 as we are considering length
    int high=mini;
    while(low<=high)
    {
        int mid=low+(high-low)/2;
        if(isCommonPrefix(strs, mid)) low=mid+1;
        else high=mid-1;
    }
    return strs[0].substr(0,(high+low)/2);
}


int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Leave a comment