LCP Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/cf0cd86c66d07222499f84ec22dbcf6cae30e848/1#
(It is also the problem of the day for 07-04-2022)
Solution:
Approach 1:
int count=0;
Arrays.sort(arr);
String a=arr[0];
StringBuilder sb=new StringBuilder();
while(count<a.length()){
boolean flag=true;
for(int i=0;i<n;i++){
if(arr[i].charAt(count)!=a.charAt(count)){
flag=false;
}
}
if(flag==true){
sb.append(a.charAt(count));
}
else{
break;
}
count++;
}
if(sb.length()==0){
return "-1";
}
else{
return sb.toString();
}
Time Complexity: O(nlogn)[GFG Time: 0.35/6.28]
Space Complexity:O(n)[Array is given]
Auxiliary Space: O(n)[StringBuilder of maximum size n will be used.]
Total Test Cases: 205
Approach 2:
int count=0;
Arrays.sort(arr);
String a=arr[0];
String b=arr[arr.length-1];
StringBuilder sb=new StringBuilder();
while(count<a.length()){
if(a.charAt(count)!=b.charAt(count)){
// flag=false;
break;
}
else{
sb.append(a.charAt(count));
}
count++;
}
if(sb.length()==0){
return "-1";
}
else{
return sb.toString();
}
Time Complexity: O(nlogn)[GFG Time: 0.32/6.28]
Space Complexity:O(n)[Array is given]
Auxiliary Space: O(n)[StringBuilder of maximum size n will be used.]
Total Test Cases: 205
Approach 1:
Here we will first sort the array in a manner that we will get the minimum value string at the start and it also ensures that all the common characters that will be present in all the strings will be definitely contained in the first string that appears in the array after sorting.
Then we will compare all the strings one by one with their characters and see whether they are the same or not. If at any instant we found they are not the same then we will break and come out of the loop, but till that time we will append the characters and increase the count variable.
This count variable also shows that the number of characters same in all the strings that are the length of the prefix.
Approach 2:
It's the same as the previous approach. However, there is only one significant difference and that is the comparison.
In the previous approach, we were comparing all the strings while in this approach we will compare only the first string and the last string after sorting.
It is so because we know that the common prefix will be present in all the strings as so in the first and last string also, and since if it is present in all the strings that it also means its length will be the same.
So if we only compare the first and last string then we will get the string that is the same in both and that will be our common prefix.
"Thanks for Reading.😇"
"Share Further To Increase Knowledge Treaure.😊"
Comments
Post a Comment