simple C++ solution (6ms) - Sort list and only compare first and last string for longest common prefix


  • 0
    A
    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) 
        {
            // basic check
            if(strs.size() == 0) return "";
            if(strs.size() == 1) return strs[0];
            
            // sort the list
            sort(strs.begin(), strs.end(), [](string& str1, string& str2)->bool{return str1<str2;});
            
            // General idea: check first and last strings for longest common prefix in sorted list        
            int j = strs.size()-1, 
                k = -1,
                min_possible_len = min(strs[0].size(), strs[j].size());
            
            while(++k!=min_possible_len && strs[0][k] == strs[j][k]);
           
            return (k == 0) ? "" : strs[0].substr(0, k);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.