Simplest and easy to understand C++ solution O(nlogn)


#1

Approach - We need to find the longest common prefix of the smallest string and the longest string in the array.

string lcp(string x, string y){
string temp;
string ans = "";
if (x.size() <= y.size())
    temp = x;
else
    temp = y;

for(int i=0; i<temp.size(); i++){
    if (x[i] == y[i]){
        ans += x[i];
    }
}
return ans;
}

string Solution::longestCommonPrefix(vector<string> &A) {
    if (A.size() == 1){
        return A[0];
    }
    if (A.size() == 0){
        return "";
    }
    sort(A.begin(), A.end());
    string ans = "";

    ans = lcp(A[0], A[A.size()-1]);

return ans;
}

#2

Sorting Array of strings takes O(NlogN) or O(N*|S|*logN) ?