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.
- Coincidencia palabra por palabra
- Coincidencia de personaje por personaje
- Divide y conquistaras
- Búsqueda binaria .
- 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++
// 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
// 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
# 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#
// 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.
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA