My Simple BruteForce Solution in O(N*Min.length()) C++


#1

string Solution::longestCommonPrefix(vector &A)
{
sort(A.begin(),A.end());
string b;
for(int i=0;i<A[0].length();i++)
{
bool flag=true;
for(int j=1;j<A.size();j++)
{
if(A[j][i]!=A[0][i])
{
flag=false;
return b;
}
}
b.push_back(A[0][i]);

}
return b;

}


#2

why use sort in the start?


#3

Sorting to get the string with min. length on index 0.


#4

If that so, after sorting you didn’t have to compare with all strings. Now that all strings are sorted then the last string will be most different from the first one. So you can just compare the first and last string to get a common prefix from them, which will be the answer.