Longest Common Prefix using Sorting

In the Longest Common Prefix using Sorting problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings.

Example

Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”}
Output: "tu"

Input2: {"baggage", "banana", "batsmen"}
Output: "ba"

Input3: {"abcd"}
Output: "abcd"

Input4: {"customer","custard"}
Output: "cust"

Approach

The approach is to sort the array of input strings (conventional sorting of strings occur in lexicographical order), in this way, we will obtain lexicographic-ally smallest and largest strings at the left and right end of the string array. It is now evident that that longest prefix common to all the strings in the array will be the longest prefix common to first (lexicographically smallest) and last (lexicographically largest) strings of the now sorted array. We process the these two strings, evaluate the largest common prefix and simply return it.

Algorithm For Longest Common Prefix using Sorting

1. define base cases (n = 0,1).
2. if size of string array is 0, the return empty string.
3. if size of string array is 1, return the only string in it as the answer(prefix string).
4. Sort the array of strings in lexicographical order.
5. Take the first and last string of the string array.
6. Find the longest common prefix among both the strings.
7. return this prefix as the final answer.

C++ Program

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

// function to return the longest common prefix from the array of strings 
string longestCommonPrefix(string arr[], int n) 
{ 
  // If size is 0, return empty string 
    if (n == 0) 
        return ""; 
        
    // if only one string is present in the array
    // it itself is the prefix
    if (n == 1) 
        return arr[0]; 
  
    // Sort the array of strings 
    sort(arr, arr + n); 
    
    // first string of the array has minimum length
    int min = arr[0].length();
    
    // common prefix of the whole array
    // is common prefix of first and last strings
    string first = arr[0], last = arr[n - 1]; 
    
    // recur until strings have common characters
    int i = 0; 
    while (i < min && first[i] == last[i]) 
        i++; 
  
    string prefix = first.substr(0, i); 
    return prefix;
} 

// main program to implement above functions 
int main() 
{ 
  string arr[] = {"tutorialcup", "tutorial", "tussle", "tumble"}; 
  int n = sizeof (arr) / sizeof (arr[0]); 

  string ans = longestCommonPrefix(arr, n); 

  if (ans.length()) 
    cout << "Longest common prefix = "<< ans; 
  else
    cout << "no common prefix found";
    
  return 0; 
}

Longest common prefix = tu

Java Program For Longest Common Prefix using Sorting

import java.io.*;
import java.util.*;
class tutorialcup 
{
   
    // function to return the longest common prefix from the array of strings 
    static String longestCommonPrefix(String arr[], int n) 
    {
    	// If size is 0, return empty string 
        if (n == 0) 
            return ""; 
            
        // if only one string is present in the array
        // it itself is the prefix
        if (n == 1) 
            return arr[0]; 
      
        // Sort the array of strings 
        Arrays.sort(arr);
        
        // first string of the array has minimum length
        int min = arr[0].length();
        
        // common prefix of the whole array
        // is common prefix of first and last strings
        String first = arr[0], last = arr[n - 1]; 
        
        // recur until strings have common characters
        int i = 0; 
        while (i < min && first.charAt(i) == last.charAt(i)) 
            i++; 
      
        String prefix = first.substring(0, i); 
        return prefix;
    } 

    // main program to implement above functions 
  public static void main (String[] args) 
  {
      String arr[] = {"tutorialcup", "tutorial", "tussle", "tumble"}; 
    	int n = arr.length; 
    
    	String ans = longestCommonPrefix(arr, n); 
    	if (ans.length() != 0) 
    		System.out.println("Longest common prefix = "+ans); 
    	else
    		System.out.println("no common prefix found");
  }
}

Longest common prefix = tu

Complexity Analysis

1. Time complexity : T(n) = O(n*m*logm)
2. Space Complexity : A(n) = O(n)

n = length of the longest string

m = number of strings in the string array.

References