leetcode 14Longest Common Prefix

leetcode 14Longest Common Prefix

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

我的解決方案：

class Solution {
public:
    string longestCommonPrefix(vector& strs)
    {
        
        if(strs.size() == 0) 
        return ;
        
        sort(strs.begin(),strs.end());
        int size = strs.size();
        int min_size = strs[0].length();
        string prefix = ;
        for(int i =0;i< min_size;++i)
        {
            char temp = strs[0][i];
            for(int j = 1;j
 
 
 
c++解決方案：
class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if(strs.empty()) return ;
        std::sort(strs.begin(),strs.end());
        string ans=strs[0];
        for (int i = 0; i < strs.size(); ++i)       
            for (int j = 0; j < ans.length() ; ++j)
            {
                if(ans[j]!=strs[i][j]) { 
                    ans=ans.substr(0,j);
                    break;
                } 
            }
        return ans;

};

//But when I changed the first loop initial value int i=1,it cost 8ms. As it is easy to proof the i=0 don't need to compare. //The loop less one time,but cost more than 4ms.



	string longestCommonPrefix(vector& strs) {
    if(strs.size() == 0) 
        return ;

    string result;
    for(int i = 0; i& strs) {
        if (strs.empty()) return ;
        for (int pos = 0; pos < strs[0].length(); pos++)
            for (int i = 1; i < strs.size(); i++)
                if (pos >= strs[i].length() || strs[i][pos] != strs[0][pos])
                    return strs[0].substr(0, pos);
        return strs[0];
    }
};


class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        int i, j, n = strs.size();
        if (n == 0) return ;
        sort(strs.begin() ,strs.begin() + n);
        for (j = 0; j < strs[0].size() && j < strs[n - 1].size() && strs[0][j] == strs[n - 1][j]; j++);
        return strs[0].substr(0, j);
    }
};




 
 
python解決方案：
 
 
class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
        if not strs:
            return 

        for i, letter_group in enumerate(zip(*strs)):
            if len(set(letter_group)) > 1:
                return strs[0][:i]
        else:
            return min(strs)


def longestCommonPrefix(self, strs):
    prefix = '';
    # * is the unpacking operator, essential here
    for z in zip(*strs):
        bag = set(z);
        if len(bag) == 1:
            prefix += bag.pop();
        else:
            break;
    return prefix;


#Divide-and-Conquer Approach, python, 44ms 
 



class Solution:
    # @param {string[]} strs
    # @return {string}

    def longestCommonPrefix(self, strs):
        if not strs: return 
        total = len(strs)
        l = min([len(x) for x in strs])
        g = 2
        while g / 2 < total:
            for i in xrange((total+g-1)/g):
                if i*g+g/2 < total:
                    while l and strs[i*g][:l] != strs[i*g+g/2][:l]: l-=1
            g *= 2
        return strs[0][:l]


 
 
??