Longest Common Prefix in an Array

In n strings,  longest common prefix among all strings is to be found

Example 1:

Input:
n = 4
arr[] = {codemummy, code, codem,
         coder}
Output: code
Explanation: "code" is the longest common
prefix in all the given strings.

Example 2:

Input: 
n = 2
arr[] = {awesome, cris}
Output: -1
Explanation: There's no common prefix
in the given strings.



method 1 :

use sorting:

sort both the string now check if the sorted strings are equal if they are equal return 1, else return 0.

c++ implementation:

  string longestCommonPrefix (string a[], int n)
{ int l=a[0].length(); string result="-1"; char current; for(int i=0;i<l;i++) { current=a[0][i]; for(int j=1;j<n;j++) { if(current!=a[j][i]) return result; } if(result=="-1") result=""; result=result+current; } return result; }
Time Complexity: O(n*l) 
where n is the no. of strings and l is the length of first string


darkmode