C++ divide and conquer solution.


  • 0
    C
     string longestCommonPrefix(vector<string>& strs) {
        int size = strs.size();
        if (size==0)
            return "";
        if (size == 1)
            return strs[0];
        vector<string> v1(strs.begin(), strs.begin()+size/2);
        vector<string> v2(strs.begin()+size/2, strs.end());
        string s1 = longestCommonPrefix(v1);
        string s2 = longestCommonPrefix(v2);
        return longestCommon(s1, s2);
    }
    
    string longestCommon(string& s1, string& s2) {
        int i = 0;
        while (i<min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }

Log in to reply
 

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