Strings: Longest Common Prefix

Problem Statement:

You are given an array of strings.

You need to find the longest common prefix in that array of strings.

Example

Input: ["flower","flow","flight"]
Output: "fl"

Solution

We have many ways to solve this problem. In this tutorial we shall solve it by using sorting method.

The solution is very simple.

We sort the array of strings.

Then compare the characters in the first and last strings in the array.

If they are same, then append the character to the result.

Else stop the comparison.

Example:
—————————————————————

If the strings are

mint, mini, mineral

After sorting the array of the strings are:

mineral, mini, mint.

Now check the first and last strings characters are check if they are same:

Pass 1:
mineral, mini, mint.
^              ^

Pass 2:
mineral, mini, mint.
 ^              ^


Pass 3:
mineral, mini, mint.
  ^              ^


Pass 4:
mineral, mini, mint.
   ^              ^
In pass 4, the characters are different, so we stop the search.

The result is "min"

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>

using namespace std;

void get_longest_common_prefix(string arr[], int n) 
{ 
  
    if (n == 0) 
        cout << "The longest common prefix is: " << ""<<endl; 
  
    if (n == 1) 
        cout << "The longest common prefix is: " << arr[0]<<endl; 
  
    // sort the array
    sort(arr, arr + n); 
   
    int length = arr[0].size();
    string result = "";

    for(int i = 0; i < length; i++)
    {
      // if the character matches, append in the result
      if(arr[0][i] == arr[n-1][i])
      {
        result += arr[0][i];
      }
      // else stop the search
      else
      {
        break;
      }
    }

   cout << "The longest common prefix is: " << result<<endl; 
} 
  
int main() 
{ 
    string arr[] = {"mint", "mini", "mineral"}; 
    int n = sizeof(arr) / sizeof(arr[0]); 

    get_longest_common_prefix(arr, n);
    return 0; 
} 

Output:

The longest common prefix is: min