Programa de Python para encontrar el prefijo común más largo usando la clasificación

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.
 

# 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

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).
Consulte el artículo completo sobre el prefijo común más largo usando la clasificación para obtener más detalles.