Given a set of strings, find the longest common prefix.
Examples:
Input : {“neveropen”, “neveropen”, “geek”, “geezer”}
Output : "gee"
Input : {"apple", "ape", "april"}
Output : "ap"
We start with an example. Suppose there are two strings- “neveropen” and “neveropen”. What is the longest common prefix in both of them? It is “neveropen”.
Now let us introduce another word “geek”. So now what is the longest common prefix in these three words ? It is “geek”
We can see that the longest common prefix holds the associative property, i.e-
LCP(string1, string2, string3)
= LCP (LCP (string1, string2), string3)
Like here
LCP (“neveropen”, “neveropen”, “geek”)
= LCP (LCP (“neveropen”, “neveropen”), “geek”)
= LCP (“neveropen”, “geek”) = “geek”
So we can make use of the above associative property to find the LCP of the given strings. We one by one calculate the LCP of each of the given string with the LCP so far. The final result will be our longest common prefix of all the strings.
Note that it is possible that the given strings have no common prefix. This happens when the first character of all the strings are not same.
We show the algorithm with the input strings- “neveropen”, “neveropen”, “geek”, “geezer” by the below figure.
Below is the implementation of above approach:
C
#include <stdio.h>#include <string.h>char* commonPrefixUtil(char* str1, char* str2){ char* result = (char*)malloc(100 * sizeof(char)); int len = strlen(str1) < strlen(str2) ? strlen(str1) : strlen(str2); for (int i = 0; i < len; i++) { if (str1[i] != str2[i]) break; result[i] = str1[i]; } result[len] = '\0'; return result;}char* commonPrefix(char* arr[], int n){ char* prefix = arr[0]; for (int i = 1; i < n; i++) { prefix = commonPrefixUtil(prefix, arr[i]); } return prefix;}int main(){ char* arr[] = { "neveropen", "neveropen", "geek", "geezer" }; int n = sizeof(arr) / sizeof(arr[0]); char* ans = commonPrefix(arr, n); if (strlen(ans)) printf("The longest common prefix is - %s", ans); else printf("There is no common prefix"); free(ans); return 0;} |
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// strings- str1 and str2string commonPrefixUtil(string& str1, string& str2){ string result = ""; int len = min(str1.length(), str2.length()); // Compare str1 and str2 for (int i = 0; i < len; i++) { if (str1[i] != str2[i]) break; result += str1[i]; } return (result);}// A Function that returns the longest common prefix// from the array of stringsstring commonPrefix (string arr[], int n){ string prefix = arr[0]; for (int i=1; i < n; i++) prefix = commonPrefixUtil(prefix, arr[i]); return (prefix);}// Driver program to test above functionint main(){ string arr[] = {"neveropen", "neveropen", "geek", "geezer"}; int n = sizeof(arr) / sizeof(arr[0]); string ans = commonPrefix(arr, n); if (ans.length()) printf ("The longest common prefix is - %s", ans.c_str()); else printf("There is no common prefix"); return (0);} |
Java
// Java Program to find the longest common prefix class GFG {// A Utility Function to find the common prefix between // strings- str1 and str2 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 String commonPrefix(String arr[], int n) { String prefix = arr[0]; for (int i = 1; i <= n - 1; i++) { prefix = commonPrefixUtil(prefix, arr[i]); } return (prefix); }// Driver program to test above function public static void main(String[] args) { String arr[] = {"neveropen", "neveropen", "geek", "geezer"}; int n = arr.length; String ans = commonPrefix(arr, n); if (ans.length() > 0) { System.out.printf("The longest common prefix is - %s", ans); } else { System.out.printf("There is no common prefix"); } }}// This code is contributed by 29AjayKumar |
Python3
# A python3 Program to find the longest # common prefix# A Utility Function to find the common # prefix between strings- str1 and str2def commonPrefixUtil(str1, str2): result = ""; n1 = len(str1) n2 = len(str2) # Compare str1 and str2 i = 0 j = 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 stringsdef commonPrefix (arr, n): prefix = arr[0] for i in range (1, n): prefix = commonPrefixUtil(prefix, arr[i]) return (prefix)# Driver Codeif __name__ =="__main__": arr = ["neveropen", "neveropen", "geek", "geezer"] n = len(arr) ans = commonPrefix(arr, n) if (len(ans)): print ("The longest common prefix is -", ans); else: print("There is no common prefix")# This code is contributed by ita_c |
C#
// C# Program to find the longest// common prefix using System;class GFG{// A Utility Function to find // the common prefix between // strings- str1 and str2 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 String commonPrefix(String []arr, int n){ String prefix = arr[0]; for (int i = 1; i <= n - 1; i++) { prefix = commonPrefixUtil(prefix, arr.GetValue(i).ToString()); } return (prefix);}// Driver Codepublic static void Main() { String []arr = {"neveropen", "neveropen", "geek", "geezer"}; int n = arr.Length; String ans = commonPrefix(arr, n); if (ans.Length > 0) { Console.Write("The longest common " + "prefix is - " + ans); } else { Console.Write("There is no common prefix"); }}}// This code is contributed// by 29AjayKumar |
Javascript
<script>// Javascript Program to find the longest common prefix // A Utility Function to find the common prefix between // strings- str1 and str2 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) { let prefix = arr[0]; for (let i = 1; i <= n - 1; i++) { prefix = commonPrefixUtil(prefix, arr[i]); } return (prefix); } // Driver program to test above function let arr=["neveropen", "neveropen", "geek", "geezer"]; let n = arr.length; let ans = commonPrefix(arr, n); if (ans.length > 0) { document.write("The longest common prefix is - ", ans); } else { document.write("There is no common prefix "); } // This code is contributed by rag2127 </script> |
Output
The longest common prefix is - gee
Time Complexity : Since we are iterating through all the strings and for each string we are iterating though each characters, so we can say that the time complexity is O(N M) where,
N = Number of strings M = Length of the largest string
Auxiliary Space : To store the longest prefix string we are allocating space which is O(M).
How to improve this ?
Please see Longest Common Prefix | Set 2 (Character by Character Matching)
This article is contributed by Rachit Belwariar. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
The approach is to sort the array of strings and compare the first and last elements of the sorted array. The common prefix between these two elements will be the longest common prefix for the entire array
Step-by-step algorithm for implementing the approach
- Define the function longest_common_prefix(arr) that takes a list of strings as input.
- Check if the input list is empty. If it is, return an empty string.
- Sort the input list of strings using the sort() method.
- Initialize the prefix to an empty string.
- Loop through the characters of the first string in the sorted list using the range() function and the len() function to get the length of the string.
- Check if the current character is the same in all strings in the input list using a generator expression and the all() function.
- If the current character is the same in all strings, add it to the prefix using the += operator.
- If the current character is not the same in all strings, break the loop using the break statement.
- Return the prefix.
- Define a sample list of strings, and call the longest_common_prefix() function with the sample list as input.
- Print the result.
C
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_STR_LEN 100char* longestCommonPrefix(char** arr, int n){ // Check if the input list is empty if (n == 0) { // If the list is empty, return an empty string return ""; } // Sort the input list of strings for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (strcmp(arr[i], arr[j]) > 0) { char* temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } // Initialize the prefix to an empty string char* prefix = (char*)malloc(sizeof(char) * MAX_STR_LEN); prefix[0] = '\0'; // Loop through the first string of the sorted list for (int i = 0; i < strlen(arr[0]); i++) { // Check if the current character is the same in all // strings in the list int match = 1; for (int j = 1; j < n; j++) { if (strlen(arr[j]) <= i || arr[j][i] != arr[0][i]) { match = 0; break; } } // If the current character is the same in all // strings, add it to the prefix if (match) { strncat(prefix, &arr[0][i], 1); } else { // If the current character is not the same in // all strings, break the loop break; } } // Return the prefix return prefix;}int main(){ // A sample list of strings char* arr[] = { "neveropen", "neveropen", "geek", "geezer" }; int n = sizeof(arr) / sizeof(arr[0]); // Print the longest common prefix printf("The longest common prefix is: %s\n", longestCommonPrefix(arr, n)); return 0;} |
C++
#include<bits/stdc++.h>using namespace std;//function to find longest common prefixstring longestCommonPrefix(vector<string> &arr){ // Check if the input list is empty if (arr.size() == 0) { // If the list is empty, return an empty string return ""; } // Sort the input list of strings sort(arr.begin(),arr.end()); // Initialize the prefix to an empty string string prefix; // Loop through the first string of the sorted list for (int i = 0; i < arr[0].length(); i++) { // Check if the current character is the same in all strings in the list bool match = true; for (int j = 1; j < arr.size(); j++) { if (arr[j].length() <= i || arr[j][i] != arr[0][i]) { match = false; break; } } // If the current character is the same in all strings, add it to the prefix if (match) { prefix+=arr[0][i]; } else{ // If the current character is not the same in all strings, break the loop break; } } // Return the prefix return prefix;}int main() { // A sample list of strings vector<string> arr= { "neveropen", "neveropen", "geek", "geezer" }; // Print the longest common prefix cout<<"The longest common prefix is: "<<longestCommonPrefix(arr); return 0;}//This code is contributed by shubhamrajput6156 |
Java
import java.util.Arrays;public class Main { public static String longestCommonPrefix(String[] arr) { // Check if the input list is empty if (arr == null || arr.length == 0) { // If the list is empty, return an empty string return ""; } // Sort the input list of strings Arrays.sort(arr); // Initialize the prefix to an empty string StringBuilder prefix = new StringBuilder(); // Loop through the first string of the sorted list for (int i = 0; i < arr[0].length(); i++) { // Check if the current character is the same in all strings in the list boolean match = true; for (int j = 1; j < arr.length; j++) { if (arr[j].length() <= i || arr[j].charAt(i) != arr[0].charAt(i)) { match = false; break; } } // If the current character is the same in all strings, add it to the prefix if (match) { prefix.append(arr[0].charAt(i)); } else { // If the current character is not the same in all strings, break the loop break; } } // Return the prefix return prefix.toString(); } public static void main(String[] args) { // A sample list of strings String[] arr = { "neveropen", "neveropen", "geek", "geezer" }; // Print the longest common prefix System.out.println("The longest common prefix is: " + longestCommonPrefix(arr)); }} |
Python3
# A function to find the longest common prefix in a list of stringsdef longest_common_prefix(arr): # Check if the input list is empty if not arr: # If the list is empty, return an empty string return "" # Sort the input list of strings arr.sort() # Initialize the prefix to an empty string prefix = "" # Loop through the first string of the sorted list for i in range(len(arr[0])): # Check if the current character is the same in all strings in the list if all(x[i] == arr[0][i] for x in arr): # If the current character is the same in all strings, add it to the prefix prefix += arr[0][i] else: # If the current character is not the same in all strings, break the loop break # Return the prefix return prefix# A sample list of stringsarr = ["neveropen", "neveropen", "geek", "geezer"]# Print the longest common prefixprint("The longest common prefix is: ", longest_common_prefix(arr)) |
C#
// C# Program to find the longest// common prefixusing System;using System.Linq;class GFG { static String longestCommonPrefix(String[] arr) { // Check if the input list is empty if (arr == null || arr.Length == 0) { // If the list is empty, return an empty string return ""; } // Sort the input list of strings Array.Sort(arr); // Initialize the prefix to an empty string string prefix = ""; // Loop through the first string of the sorted list for (int i = 0; i < arr[0].Length; i++) { // Check if the current character is the same in // all strings in the list bool match = true; for (int j = 1; j < arr.Length; j++) { if (arr[j].Length <= i || arr[j][i] != arr[0][i]) { match = false; break; } } // If the current character is the same in all // strings, add it to the prefix if (match) { prefix += arr[0][i]; } else { // If the current character is not the same // in all strings, break the loop break; } } // Return the prefix return (prefix); } public static void Main(string[] args) { String[] arr = { "neveropen", "neveropen", "geek", "geezer" }; // Print the longest common prefix Console.WriteLine("The longest common prefix is: " + longestCommonPrefix(arr)); }}//This Code is contributed by Akshay Tripathi(akshaytripathi19410) |
Javascript
function longestCommonPrefix(arr){ // Check if the input list is empty if (!arr.length) { // If the list is empty, return an empty string return ""; } // Sort the input list of strings arr.sort(); // Initialize the prefix to an empty string let prefix = ""; // Loop through the first string of the sorted list for (let i = 0; i < arr[0].length; i++) { // Check if the current character is the same in all strings in the list if (arr.every((x) => x[i] === arr[0][i])) { // If the current character is the same in all strings, add it to the prefix prefix += arr[0][i]; } else { // If the current character is not the same in all strings, break the loop break; } } // Return the prefix return prefix;}// A sample list of stringsconst arr = ["neveropen", "neveropen", "geek", "geezer"];// Print the longest common prefixconsole.log("The longest common prefix is: ", longestCommonPrefix(arr)); |
Output
The longest common prefix is: gee
Time complexity: O(NMlogM), where N is the number of strings in the input list and M is the length of the longest string in the input list. The sort() method used to sort the input list has a time complexity of O(NlogN), and the loop through the characters in the first string has a time complexity of O(M). The all() function inside the loop has a time complexity of O(N), where N is the number of strings in the input list. Therefore, the total time complexity is O(NlogN + NM).
Auxiliary space: O(1). The function uses a constant amount of auxiliary space, since it only stores a prefix string of length at most M.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
