Longest Common Prefix Using Sorting

Introduction

This blog will discuss the approach using Sorting to solve the longest common prefix problem. Before jumping into the problem to get the longest common prefix, let’s first understand what is the longest common prefix,

The longest common prefix is the longest substring which is common among the array of dissimilar strings.

For example:

Input:- 

Output:- cod

Explanation:- 

In these four given words, the longest possible common prefix is “cod”.

Approach

In this approach, we need to find the longest common prefix using sorting. In this, after sorting all the strings, we need to store the minimum value of the first and the last string in a variable and find the longest common prefix of the given first and last string after sorting all the strings.

Algorithm

Step 1. Create a function ‘getResult()’ that will accept 2 parameters, i.e., one vector of strings ‘input’ and second is the size of that vector. 

Step 2. Return an empty string if the size of the vector received is zero. 

Step 3. Return the first string of the vector if the size of the ‘input’ vector is 1.

Step 4.  Sort all the strings in the ‘input’ vector.

Step 5. Assign the minimum value of the size of the first and last string of the ‘input’ to an integral variable ‘temp’.

Step 6. Initialize a variable ‘count’ with zero.

Step 7. Make an iteration using the ‘while’ loop, and increment the value of ‘count’, if it is less than the value of ‘temp’ and the character at the ith index of both the first and last string is the same.

Step 8. Take a substring using ‘substr’ function which will take the initial and ending point of the substring to be taken, and store it in a string variable ‘result’.

Step 8. Return ‘result’

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

// Function to return the longest common prefix
string getResult(vector<string> input, int n)
{

   // If size is 0
   if (n == 0)
   {
       return "";
   }

   if (n == 1)
   {
       return input[0];
   }

   // Sort the given input array
   sort(input.begin(), input.end());

   // minimum length of both first and last string
   int temp = min(input[0].size(), input[n - 1].size());

   // find common prefix using first and last string
   string first = input[0], last = input[n - 1];
   int i = 0;

   while (i < temp && first[i] == last[i])
   {
       i++;
   }

   // Get substring using substr function
   string result = first.substr(0, i);
   return result;
}

// Driver Code
int main()
{
   vector<string> input = {"codingninjas", "code", "coding", "codingbook"};
   int n = input.size();

   cout << "The longest common prefix is: " << getResult(input, n);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The longest common prefix is: cod

Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, we are traversing the complete preorder vector once and constructing the binary tree and using push function and other recursive calls which will take at max ‘N’ computational time, therefore, the overall time complexity is O(N).

Space Complexity: O(N)

As we are using ‘N’ extra space to store the binary tree, therefore, the overall space complexity will be O(N).

Check out this array problem - Merge 2 Sorted Arrays

Refer to know about :  Topological sort