LeetCode

LeetCode - Longest Common Prefix

2013.12.1 23:23

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

Solution:

　　For two string s1 and s2, compare the elements from the beginning, when the end or the first mismatch is found, the common prefix is found.

　　For n strings s[n], perform (n - 1) times such comparings. If the current common prefix is already empty "", then the latter comparison is meaningless and cancelled.

　　Time complexity is O(n * max(strlen(s[i]))), that means the comparison can be performed at most (n - 1) times, and no single comparison will go longer than the longest string amongst s[n]. Space complexity is O(1).

　　Actually, if we find out the shortest string s_min amongst s[n], and start the first comparison from the shortest string. We'll gain a time complexity of O(n * min(strlen(s[i]))). Space complexity remains O(1).

　　Here is an example to show why order of the data matters:

　　　　['aaa', ''aaa', 'aaa', 'd']

　　　　['d', 'aaa', 'aaa', 'aaa']

　　　　The time needed for the two dataset above would be different, since order is different. It's better to put short ones on the front.

Accepted code:

// 1RE, 1AC
#include <algorithm>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int n = strs.size();
        // 1RE here, didn't consider the case when $strs is empty.
        if(n <= 0){
            return "";
        }
        string res = strs[0];
        
        int i;
        for(i = 1; i < n; ++i){
            res = commonPrefix(res, strs[i]);
            if(res == ""){
                break;
            }
        }
        
        return res;
    }
private:
    string commonPrefix(string s1, string s2) {
        if(s1.length() > s2.length()){
            return commonPrefix(s2, s1);
        }
        
        int len1, len2;
        
        len1 = s1.length();
        len2 = s2.length();
        int i;
        for(i = 0; i < len1; ++i){
            if(s1[i] != s2[i]){
                break;
            }
        }
        
        return s1.substr(0, i);
    }
};