Leetcode——最长公共前缀

第一次做，用了暴力破解：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        length = 0
        text = ""
        if "" in strs:
            return ""
        if len(strs) == 1:
            return strs[0]
        for each in strs:
            if len(each) > length:
                length = len(each) + 1
                idx = strs.index(each)
        
        for j in range(1, length):
            for tmp in strs:
                if strs[idx][:j] != tmp[:j]:
                    return  text
            text = strs[idx][:j]
        return text        

看到一个解法很精妙，记录一下：
原理是在python里字符串是可以比较大小的，按照其ascall码大小从前往后比，和字符串长短无关。例如 :
aaa < z
abc > aba
因此只要把列表里最大的和最小的字符串拿出来比较就行了，它会一直比较到字符串中不一样的位置，例：
strs = [‘abb’, ‘acb’, ‘acc’, ‘ad’]
max(strs) = ‘ad’
min(strs)==‘abb’

    def longestCommonPrefix(self, strs):
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1

还有一种：
利用python的zip函数，把str看成list然后把输入看成二维数组，左对齐纵向压缩，然后把每项利用集合去重，之后遍历list中找到元素长度大于1之前的就是公共前缀

    def longestCommonPrefix(self, strs):
        if not strs: return ""
        ss = list(map(set, zip(*strs)))
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res