share my solution solved by Devide & Conquer Alg, which takes 6ms


  • 0
    C

    class Solution {
    public:
    string longestCommonPrefix(vector<string>& strs) {

    	size_t nums_str = strs.size();
    	if (0 == nums_str)
    	{
    		return "";
    	}
    	else if (1 == nums_str)
    	{
    		return strs[0];
    	}
    
    	string first_part_prefix = Compare(0, nums_str / 2-1, strs);
    	string second_part_prefix = Compare(nums_str / 2 , nums_str - 1, strs);
    
    	size_t fir_part_len = first_part_prefix.size();
    	size_t sec_part_len = second_part_prefix.size();
    	string ans_str;
    	for (size_t fidx = 0, sidx = 0;
    		fidx<fir_part_len && sidx<sec_part_len;
    		fidx++, sidx++)
    	{
    		if (first_part_prefix[fidx] != second_part_prefix[sidx])
    		{
    			break;
    		}
    
    		ans_str.push_back(first_part_prefix[fidx]);
    	}
    
    	return ans_str;
    }
    

    private:
    string Compare(size_t first_idx, size_t last_idx, vector<string>& strs)
    {
    if (first_idx == last_idx)
    {
    return strs[first_idx];
    }

    	string first_part_prefix;
    	string second_part_prefix;
    	size_t interval = last_idx - first_idx;
    	if (1 == interval)
    	{
    		first_part_prefix = strs[first_idx];
    		second_part_prefix = strs[last_idx];
    	}
    	else
    	{
    		first_part_prefix = Compare(first_idx, first_idx + interval/2, strs);
    		second_part_prefix = Compare(first_idx+interval/2 + 1, last_idx, strs);
    	}
    
    	size_t fir_part_len = first_part_prefix.size();
    	size_t sec_part_len = second_part_prefix.size();
    	string ans_str;
    	for (size_t fidx = 0, sidx = 0;
    		fidx<fir_part_len && sidx<sec_part_len;
    		fidx++, sidx++)
    	{
    		if (first_part_prefix[fidx] != second_part_prefix[sidx])
    		{
    			break;
    		}
    
    		ans_str.push_back(first_part_prefix[fidx]);
    	}
    
    	return  ans_str;
    }
    

    };


Log in to reply
 

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