Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

array
strings

How to find the longest common prefix in an array of strings

Educative Answers Team

A prefix is a collection of characters at the beginning of a string. For instance, “mi” is a prefix of “mint” and the longest common prefix between “mint”, “mini”, and “mineral” is “min”.

Algorithm

  1. Sort the array of strings in alphabetical order.

  2. Compare the characters in the first and last strings in the array. Since the array is sorted, common characters among the first and last element will be common among all the elements of the array.

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

    2.2. Else, stop the comparison – result contains the longest common prefix among the strings in the array.

The following illustration shows the algorithm in action:

Array of strings
1 of 6

Implementation

#include <iostream>
#include <string>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  string arr[3] = {"mint", "mini", "mineral"}; 
  int size = sizeof(arr)/sizeof(*arr);
  // The longest common prefix of an empty array is "".
  if (size == 0){
    cout << "Longest common prefix:" << "" <<endl;
  }
    // The longest common prefix of an array containing 
    // only one element is that element itself.
  else if (size == 1){
    cout << "Longest common prefix:" << arr[0] <<endl;
  }
  else{
    // Sort the array
    std::sort(arr, arr + size);
    int length = arr[0].size();
    string result = "";
    // Compare the first and the last string character
    // by character.
    for(int i = 0; i < length; i++){
      // If the characters match, append the character to the result.
      if(arr[0][i] == arr[size-1][i]){
        result += arr[0][i];
      }
      // Else stop the comparison.
      else{
        break;
      }
    }
    cout << "Longest common prefix: " << result <<endl; 
  }
  return 0;
}

RELATED TAGS

array
strings
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring