0. 题目

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

Example 1:
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.

1. C++版本

首先想到的测试用例如下：

思想：对于一系列字符串，可以先确定长度minLen最小的字符串，然后依次minLen比较每个字符串的是不是一样

 string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty())
            return "";
        int minLen = strs[0].size();
        string common_str = strs[0];
        for (int i=0; i<strs.size(); i++) {
           if (minLen > strs[i].size()) {
               minLen = strs[i].size();
               common_str = strs[i];
           }
        }
        for (int i=0; i<minLen; ++i) {
            for (int j=0; j<strs.size(); ++j) {
                if (common_str[i] != strs[j][i])
                    return common_str.substr(0, i);
            }
            if (i == minLen-1)
                return common_str;
        }
        return "";
    }

2. python版本

注： python中min函数用法，不能传入空list！

    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        common_str = min(strs, key=len)
        min_len = len(common_str)
        for i in range(min_len):
            for j in range(len(strs)):
                 if common_str[i] != strs[j][i]:
                     return common_str[0:i]
            if i == min_len-1:
                return common_str
        return ""

看了下提交python高赞版本，发现这个版本可以优化。 没必要判断i == min_len-1，当初加这句是考虑['flow', 'fl', '12345', 'test']这种情况，其实 if common_str[i] != strs[j][i]: return common_str[0:i] 就可以返回""。
优化如下：

    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        common_str = min(strs, key=len)
        min_len = len(common_str)
        for i in range(min_len):
            for j in range(len(strs)):
                 if common_str[i] != strs[j][i]:
                     return common_str[0:i]
        return common_str

更加pythonic高赞版本 引用https://leetcode.com/problems/longest-common-prefix/discuss/6918/Short-Python-Solution

 def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        shortest = min(strs,key=len)
        for i, ch in enumerate(shortest):
            for other in strs:
                if other[i] != ch:
                    return shortest[:i]
        return shortest