Prefijo común más largo mediante clasificación – Part 1

Declaración del problema: dado un conjunto de strings, encuentre el prefijo común más largo.
Ejemplos: 
 

Input: {"geeksforgeeks", "geeks", "geek", "geezer"}
Output: "gee"

Input: {"apple", "ape", "april"}
Output: "ap"

El prefijo común más largo para una array de strings es el prefijo común entre 2 strings más diferentes. Por ejemplo, en la array dada {“manzana”, “simio”, “cebra”}, no hay un prefijo común porque las 2 strings más diferentes de la array “simio” y “cebra” no comparten ningún carácter inicial. 
Hemos discutido cinco enfoques diferentes en las publicaciones a continuación. 
 

1. Coincidencia palabra por palabra
2. Coincidencia de personaje por personaje
3. Divide y conquistaras
4. Búsqueda binaria .
5. Usando Trie)

En esta publicación se analiza un nuevo método basado en la clasificación. La idea es ordenar la array de strings y encontrar el prefijo común de la primera y la última string de la array ordenada.
 

// C++ program to find longest common prefix
// of given array of words.
#include<iostream>
#include<algorithm>
 
using namespace std;
 
// Function to find the longest common prefix
string longestCommonPrefix(string ar[], int n)
{
 
    // If size is 0, return empty string
    if (n == 0)
        return "";
 
    if (n == 1)
        return ar[0];
 
    // Sort the given array
    sort(ar, ar + n);
 
    // Find the minimum length from
    // first and last string
    int en = min(ar[0].size(),
                 ar[n - 1].size());
 
    // Now the common prefix in first and
    // last string is the longest common prefix
    string first = ar[0], last = ar[n - 1];
    int i = 0;
    while (i < en && first[i] == last[i])
        i++;
 
    string pre = first.substr(0, i);
    return pre;
}
 
// Driver Code
int main()
{
    string ar[] = {"geeksforgeeks", "geeks",
                           "geek", "geezer"};
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << "The longest common prefix is: "
         << longestCommonPrefix(ar, n);
    return 0;
}
 
// This code is contributed by jrolofmeister

// Java program to find longest common prefix of
// given array of words.
import java.util.*;
 
public class GFG
{
    public String longestCommonPrefix(String[] a)
    {
        int size = a.length;
 
        /* if size is 0, return empty string */
        if (size == 0)
            return "";
 
        if (size == 1)
            return a[0];
 
        /* sort the array of strings */
        Arrays.sort(a);
 
        /* find the minimum length from first and last string */
        int end = Math.min(a[0].length(), a[size-1].length());
 
        /* find the common prefix between the first and
           last string */
        int i = 0;
        while (i < end && a[0].charAt(i) == a[size-1].charAt(i) )
            i++;
 
        String pre = a[0].substring(0, i);
        return pre;
    }
 
    /* Driver Function to test other function */
    public static void main(String[] args)
    {
        GFG gfg = new GFG();
        String[] input = {"geeksforgeeks", "geeks", "geek", "geezer"};
        System.out.println( "The longest Common Prefix is : " +
                                   gfg.longestCommonPrefix(input));
    }
}

# Python 3 program to find longest
# common prefix of given array of words.
def longestCommonPrefix( a):
     
    size = len(a)
 
    # if size is 0, return empty string
    if (size == 0):
        return ""
 
    if (size == 1):
        return a[0]
 
    # sort the array of strings
    a.sort()
     
    # find the minimum length from
    # first and last string
    end = min(len(a[0]), len(a[size - 1]))
 
    # find the common prefix between
    # the first and last string
    i = 0
    while (i < end and
           a[0][i] == a[size - 1][i]):
        i += 1
 
    pre = a[0][0: i]
    return pre
 
# Driver Code
if __name__ == "__main__":
 
    input = ["geeksforgeeks", "geeks",
                     "geek", "geezer"]
    print("The longest Common Prefix is :" ,
                 longestCommonPrefix(input))
 
# This code is contributed by ita_c

// C# program to find longest common prefix of
// given array of words.
using System;
         
public class GFG {
     
    static string longestCommonPrefix(String[] a)
    {
        int size = a.Length;
 
        /* if size is 0, return empty string */
        if (size == 0)
            return "";
 
        if (size == 1)
            return a[0];
 
        /* sort the array of strings */
        Array.Sort(a);
 
        /* find the minimum length from first
        and last string */
        int end = Math.Min(a[0].Length,
                            a[size-1].Length);
 
        /* find the common prefix between the
        first and last string */
        int i = 0;
        while (i < end && a[0][i] == a[size-1][i] )
            i++;
 
        string pre = a[0].Substring(0, i);
        return pre;
    }
 
    /* Driver Function to test other function */
    public static void Main()
    {
         
        string[] input = {"geeksforgeeks", "geeks",
                                 "geek", "geezer"};
                                  
        Console.WriteLine( "The longest Common"
                              + " Prefix is : "
                  + longestCommonPrefix(input));
    }
}
 
// This code is contributed by Sam007.

<script>
// Javascript program to find longest common prefix of
// given array of words.
     
    function longestCommonPrefix(a)
    {
        let size = a.length;
   
        /* if size is 0, return empty string */
        if (size == 0)
            return "";
   
        if (size == 1)
            return a[0];
   
        /* sort the array of strings */
        a.sort();
   
        /* find the minimum length from first and last string */
        let end = Math.min(a[0].length, a[size-1].length);
   
        /* find the common prefix between the first and
           last string */
        let i = 0;
        while (i < end && a[0][i] == a[size-1][i] )
            i++;
   
        let pre = a[0].substring(0, i);
        return pre;
    }
     
    /* Driver Function to test other function */
    let input=["geeksforgeeks", "geeks", "geek", "geezer"];
    document.write( "The longest Common Prefix is : " +
                                   longestCommonPrefix(input));
       
     
    // This code is contributed by rag2127
</script>

Producción: 
 

The longest common prefix is : gee

Complejidad de tiempo: O (MAX * n * log n) donde n es el número de strings en la array y MAX es el número máximo de caracteres en cualquier string. Tenga en cuenta que la comparación de dos strings tomaría como máximo el tiempo O (MAX) y para ordenar n strings, necesitaríamos el tiempo O (MAX * n * log n).

Complejidad espacial: O(1) 

Este artículo es una contribución de Saloni Baweja . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.