My Easy soln C++


#1

string Solution::longestCommonPrefix(vector &A) {
string ans="";
sort(A.begin(),A.end());
int n=A.size();
string s=A[n-1];

    for(int j=0;j<A[0].size();j++)
    {
        if(A[0][j]==A[n-1][j])
        ans+=A[n-1][j];
        else
        break;
    }

return ans;
}

#2

Can you explain the traversing part, I mean how you are coming to 2nd string in the vector?


#3

He doesn’t need to come to the second string.

He is sorting all the strings in the vector. So order of strings is changed to make sure the first string is always the shortest and the last to be the longest.

At the end he only compares first and the last string and takes the prefix of these two. Whatever letters are common between these two are guaranteed to be common between all the strings between them. So the solution is O (N * log N) + O(K) where N = number of strings in the vector and K = common characters between all the strings.


#4

string Solution::longestCommonPrefix(vector &A) {
string pref=A[0];
for(auto x: A){
string t;
for(int i=0;i<min(x.size(),pref.size());i++){
if(pref[i]==x[i])t.push_back(pref[i]);
else break;
}
pref=t;
}
return pref;
}