Dado un conjunto de strings, encuentre el prefijo común más largo.
Ejemplos:
Input: str[] = {geeksforgeeks, geeks, geek, geezer} Output: gee Input: str[] = {apple, ape, april} Output: ap
Enfoques anteriores: Set1 | Conjunto2 | Conjunto3 | Conjunto4 | Enfoque Set5
:
- Ordenar el conjunto dado de N strings.
- Compare la primera y la última string en la array ordenada de strings.
- La string con caracteres de prefijo que coincidan en la primera y la última string será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ Program to find the longest common prefix #include <bits/stdc++.h> using namespace std; // A Utility Function to find the common prefix between // first and last strings string commonPrefixUtil(string str1, string str2) { string result; int n1 = str1.length(), n2 = str2.length(); // Compare str1 and str2 for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) { if (str1[i] != str2[j]) break; result.push_back(str1[i]); } return (result); } // A Function that returns the longest common prefix // from the array of strings void commonPrefix(string arr[], int n) { // sorts the N set of strings sort(arr, arr + n); // prints the common prefix of the first and the // last string of the set of strings cout << commonPrefixUtil(arr[0], arr[n - 1]); } // Driver Code int main() { string arr[] = { "geeksforgeeks", "geeks", "geek", "geezer" }; int n = sizeof(arr) / sizeof(arr[0]); commonPrefix(arr, n); return 0; }
Java
// A Java program to find the longest common prefix import java.util.Arrays; class GFG { // A Utility Function to find the common prefix between // first and last strings static String commonPrefixUtil(String str1, String str2) { String result = ""; int n1 = str1.length(), n2 = str2.length(); // Compare str1 and str2 for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) { if (str1.charAt(i) != str2.charAt(j)) { break; } result += str1.charAt(i); } return (result); } // A Function that returns the longest common prefix // from the array of strings static void commonPrefix(String arr[], int n) { // sorts the N set of strings Arrays.sort(arr); // prints the common prefix of the first and the // last String of the set of strings System.out.println(commonPrefixUtil(arr[0], arr[n - 1])); } // Driver Code public static void main(String[] args) { String arr[] = {"geeksforgeeks", "geeks", "geek", "geezer"}; int n = arr.length; commonPrefix(arr, n); } } /* This JAVA code is contributed by 29AjayKumar*/
Python3
# A Python 3 Program to find the # longest common prefix # A Utility Function to find the common # prefix between first and last strings def commonPrefixUtil(str1, str2): n1 = len(str1) n2 = len(str2) result = "" # Compare str1 and str2 j = 0 i = 0 while(i <= n1 - 1 and j <= n2 - 1): if (str1[i] != str2[j]): break result += (str1[i]) i += 1 j += 1 return (result) # A Function that returns the longest # common prefix from the array of strings def commonPrefix(arr, n): # sorts the N set of strings arr.sort(reverse = False) # prints the common prefix of the first # and the last string of the set of strings print(commonPrefixUtil(arr[0], arr[n - 1])) # Driver Code if __name__ == '__main__': arr = ["geeksforgeeks", "geeks", "geek", "geezer"] n = len(arr) commonPrefix(arr, n) # This code is contributed by # Sanjit_Prasad
C#
// C# Program to find the longest // common prefix using System; class GFG { // A Utility Function to find the common // prefix between first and last strings static String commonPrefixUtil(String str1, String str2) { string result = ""; int n1 = str1.Length, n2 = str2.Length; // Compare str1 and str2 for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) { if (str1[i] != str2[j]) break; result += (str1[i]); } return (result); } // A Function that returns the longest // common prefix from the array of strings static void commonPrefix(String []arr, int n) { // sorts the N set of strings Array.Sort(arr); // prints the common prefix of the first // and the last String of the set of strings Console.Write(commonPrefixUtil(arr[0], arr[n - 1])); } // Driver Code public static void Main() { String []arr = {"geeksforgeeks", "geeks", "geek", "geezer"}; int n = arr.Length; commonPrefix(arr, n); } } // This code is contributed by 29AjayKumar
PHP
<?php // A PHP Program to find the longest // common prefix // A Utility Function to find the common // prefix between first and last strings function commonPrefixUtil($str1, $str2) { $result = ""; $n1 = strlen($str1); $n2 = strlen($str2); // Compare str1 and str2 for ($i = 0, $j = 0; $i <= $n1 - 1 && $j <= $n2 - 1; $i++, $j++) { if ($str1[$i] != $str2[$j]) break; $result = $result.$str1[$i]; } return ($result); } // A Function that returns the longest // common prefix from the array of strings function commonPrefix(&$arr, $n) { // sorts the N set of strings sort($arr); // prints the common prefix of the first // and the last string of the set of strings echo commonPrefixUtil($arr[0], $arr[$n - 1]); } // Driver Code $arr = array("geeksforgeeks", "geeks", "geek", "geezer" ); $n = sizeof($arr); commonPrefix($arr, $n); // This code is contributed by ita_c ?>
Javascript
<script> // A Javascript program to find the longest common prefix // A Utility Function to find the common prefix between // first and last strings function commonPrefixUtil(str1,str2) { let result = ""; let n1 = str1.length, n2 = str2.length; // Compare str1 and str2 for (let i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) { if (str1[i] != str2[j]) { break; } result += str1[i]; } return (result); } // A Function that returns the longest common prefix // from the array of strings function commonPrefix(arr,n) { // sorts the N set of strings arr.sort(); // prints the common prefix of the first and the // last String of the set of strings document.write(commonPrefixUtil(arr[0], arr[n - 1])+"<br>"); } // Driver Code let arr=["geeksforgeeks", "geeks", "geek", "geezer"]; let n = arr.length; commonPrefix(arr, n); // This code is contributed by avanitrachhadiya2155 </script>
Producción:
gee
Complejidad de tiempo: O(N * log N)