给定一组字符串，找到最长的公共前缀。 例如：
null
Input: str[] = {geeksforgeeks, geeks, geek, geezer}Output: geeInput: str[] = {apple, ape, april}Output: ap
以前的做法： Set1 | Set2 | Set3 | Set4 | Set5 方法：
- 对给定的N个字符串进行排序。
- 比较排序字符串数组中的第一个字符串和最后一个字符串。
- 第一个和最后一个字符串中前缀字符匹配的字符串将是答案。
以下是上述方法的实施情况：
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> |
输出：
gee
时间复杂性： O（N*logn）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
