letcode[014] 最长公共前缀

题目014

题目地址：最长公共前缀

1. 从最直观的角度来说，将字符串拆解成矩阵然后对比最直观（方法3），但并不容易直接想到转换为矩阵的方法。
2. 所以转念一想，还是遍历每个数据的方法最暴力最容易实现。

思路1：自拟思路——从最短字符串入手

获取最短的字符串，然后依次取最短字符串的左边n位，和其他字符串的左边n位去重，如果去重后列表长度大于1，则表示n-1位是公共前缀。n-1==0时，就是没有公共前缀。
总结：注意if判断时候的条件之间的关系，各&或|关系间使用括号区隔，以免引起问题
用时：52 ms

strs=["flower","flow","flight"]
strs=["dog","racecar","car"]
strs=["abcdef","abcdef","bcdef","abcdef","abcdef"]
strs=[]

def longestCommonPrefix1(strs):
    if len(strs)==0:
        return ""
    else:
        #获取最短字符串的长度和字符串
        length=[len(s) for s in strs]
        min_length=min(length)
        min_str=strs[length.index(min_length)]
        for i in range(min_length+1):
            ls=[s[:i+1] for s in strs]
            if i==0 & len(set(ls))>1:
                return ""
            elif len(set(ls))>1:
                return min_str[:i]
            elif (i==min_length) & (len(set(ls))==1):
                return min_str

思路2：网友思路——取任意字符串，从右逐位减少字符，进行查找

取第一个字符串的全部，然后使用find函数遍历所有字符串（find从左到右查询，如果有完全匹配的则返回0，否则返回-1），没匹配上则将第一个字符串从右往左减少一位，继续匹配；直到第一位字符串为空。
总结：这是排行靠前的方法，要知道有find函数，可能是最为普遍的思路了。
用时：36 ms

def longestCommonPrefix2(strs):
        if len(strs) == 0:
            return ""
        prefix = strs[0]
        for s in strs:
            while s.find(prefix) != 0:
                prefix = prefix[0:len(prefix) - 1]
                if prefix == "":
                    return prefix
        return prefix

思路3：网友思路——字符串拆解矩阵

利用zip函数，将字符串打散，将相同位置的字符组成一个元组，通过判断元组的重复值即可知最长公共前缀。
总结：这也是排行靠前的方法，要知道map函数的特性。
用时：44 ms

def longestCommonPrefix3(strs):
    res = ""
    if len(strs) == 0:
        return ""
    for each in zip(*strs):#zip()函数用于将可迭代对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表
        if len(set(each)) == 1:#利用集合创建一个无序不重复元素集
            res += each[0]
        else:
            return res
    return res