leetcode 14：最小公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

这是道easy题，我的方法：（很笨）

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        minStrLen = len(strs[0])
        for i in range(1, len(strs)):
            if len(strs[i]) < minStrLen:
                minStrLen = len(strs[i])
        res = ''
        for i in range(minStrLen):
            tar = strs[0][i] 
            for j in range(len(strs)):
                if strs[j][i] != tar:
                    return res
            res = res + tar
        return res

看了一下别人写的代码，发现了新的世界，所以记录一下。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: 
            return ""
        New = list(map(set,zip(*strs))) ##zip将string中的每个元素对位压缩，然后去重形成相应的集合，map功能实现zip和set的映射    (这里是精髓，如果是例程1的话，结果就是[set(['f']), set(['l']), set(['i', 'o']), set(['g', 'w'])]，那么其实就只要把去重结果长度为1的子项提出来就可以了。）
        Prefix = ''
        for i, x in enumerate(New):
            x = list(x)
            if len(x) > 1:
                i = i+1
                break
            Prefix = Prefix+x[0]
        return Prefix

还看到另外一个解法，也挺漂亮的。

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ''
 
        if len(strs) == 1:
            return strs[0]
        # 注意python里的min和max指的是把数组里的每个字符串项的ascii码相加以后的最小/最大值
        a = min(strs)
        b = max(strs)
 
        for i in range(len(a)):
            if a[i] != b[i]:
                return a[:i]
        return a