Divide-and-Conquer Approach for Longest Common Prefix problem, C++


  • 0
    F
    string longestPrefix(vector<string> &lst, int p, int q) {
        if (p < q) {
            string left_prefix = longestPrefix(lst, p, (p+q)/2);
            string right_prefix = longestPrefix(lst, (p+q)/2 + 1, q);
            return findCommonPrefix(left_prefix, right_prefix);
        }
        return lst[p];
    }
    
    string findCommonPrefix(string a, string b) {
        string prefix = "";
        int i = 0;
        int n = (a.size() < b.size()) ? a.size() : b.size();
        while (i < n && a[i] == b[i]) {
            prefix += a[i];
            i++;
        }
        return prefix;
    }
    
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.size() < 1) 
            return "";
        return longestPrefix(strs, 0, strs.size()-1);
    }

Log in to reply
 

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