LongestCommonPrefix_Recursion.cpp

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int len_s = strs.size();
        if(len_s == 0) return "";
        return longestCommonPrefix(strs, 0, len_s - 1);
    }
    string longestCommonPrefix(vector<string>& strs, int l, int r){
        if(l == r){
            return strs[l];
        }   
        else{
            int mid = (l + r)/2;
            string l_part = longestCommonPrefix(strs, l, mid);
            string r_part = longestCommonPrefix(strs, mid+1, r);
            return calculateCommonPrefix(l_part, r_part);
        }    
    }
    
    string calculateCommonPrefix(string& l, string& r){
        int minLen = min(l.size(), r.size());
        for(int i = 0; i < minLen; i++){
            if(l[i] != r[i])
                return l.substr(0, i);
        }
        return l.substr(0, minLen);
    }
};