LeetCode: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

---

There are two ways for this problem. One is divide and conquer, getting the common prefix from the left part and the right part recursively. The other one is to iterate the list from the start and compute common prefix each time. I wrote the first one in C++ and the second one in Python.

C++ Code:

/* common_prefix
 * goal: to find common prefix of two strings
 * @param left: string 1
 * @param right: string 2
 * return: longest common prefix
 */
string common_prefix(const string &left, const string &right){
    string com_pre = "";
    int upperbound = min(left.size(), right.size());
    for(int i=0; i < upperbound; ++i){
        if(left[i] == right[i]){
            com_pre += left[i];
        }else{
            break;
        }
    }
    
    return com_pre;
}

/*
 * func: longest_common_prefix_helper
 * goal: helper function of longest_common_prefix to be called recursively
 * @param strs: vector of strings
 * @param start: start index
 * @param end: end index
 * return: longest common prefix
 */
string longest_common_prefix_helper(const vector<string> &strs, int start, int end){
    if(start >= end){
        return strs[start];
    }
    
    int mid = start + (end-start)/2;
    
    string left_prefix = longest_common_prefix_helper(strs, start, mid);
    string right_prefix = longest_common_prefix_helper(strs, mid+1, end);
    
    return common_prefix(left_prefix, right_prefix);
}

/*
 * func: longest_common_prefix
 * goal: to find the longest common prefix among an array of strings
 * @param strs: vector of strings
 * return: longest common prefix
 */
/*
 * use divide and conquer, compute common prefix of each two pairs
 * complexity: time O(n), space O(1) if stack doesn't count
 */
string longest_common_prefix(const vector<string> &strs){
    if(strs.size() == 0){
        return "";
    }
    if(strs.size() == 1){
        return strs[0];
    }
    
    return longest_common_prefix_helper(strs, 0, strs.size()-1);
}

Python Code:

# func: find the longest common prefix
# @param strs: list of strings
# @return: the longest common prefix
def longest_common_prefix(strs):
    if not strs:
        return ""
    else:
        ret = strs[0]
        for i in xrange(1, len(strs)):
            j = 0
            while j < len(ret) and j < len(strs[i]) and ret[j] == strs[i][j]:
                j += 1
            ret = ret[:j]

        return ret

I also tried the second one in C++ and compared its performance with those one in divide and conquer. Surprisingly the more complicated one uses less time(16ms vs 40ms). I cannot figure out why because they have the same time complexity and recursive one took more space.