[LeetCode]14-最长公共前缀

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

解法1: 取字符串逐一比较

class Solution:
    def longestCommonPrefix(self, strs):
        # 排除异常情况, 字符串为空或只有1个
        if strs is None or len(strs) == 0:
            return ""
        elif len(strs) == 1:
            return strs[0]
        minmun = len(strs[0])   #取出最短字符串的长度
        for each in strs:
            if each == "":  #如果有空字符串直接返回
                return ""
            if len(each) < minmun:
                minmun = len(each)
        res = ""    #记录最长前缀
        for i in range(0, minmun):
            pre = strs[0][:i + 1]
            for each in strs:
                if pre == each[:i + 1]:
                    res = pre
                else:
                    return pre[:i]
        return res

解法2: 逐一比较的简化版

依然先算了最短字符串的长度, 也可以省掉这次计算直接循环取公共前缀.

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:    #排除 strs 为空的情况
            return ""
        if len(strs) == 1:
            return strs[0]
        minmun = min([len(each) for each in strs])    #取最短长度
        end = 0    #记录公共前缀字符数
        while end < minmun:
            for each in strs:
                if each[end] != strs[0][end]:
                    return strs[0][:end]
            end += 1
        return strs[0][:end]

解法3: 用zip函数

zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。
在 Python 3.x 中为了减少内存，zip() 返回的是一个对象.如需展示列表，需手动 list() 转换.

Python 3 中 zip() 函数的用法:

a = [1, 2, 3]
b = [4, 5, 6]
c = [1, 2, 3, 4, 5, 6]

zipped = zip(a, b, c)      # zip 对象<zip object at 0x1074aad88>
list(zipped)    # 转成list类型
# (1, 4, 1), (2, 5, 2), (3, 6, 3)
zip_list = zip(*zipped)    #zip(*) 是 zip() 的逆向
# (1, 2, 3), (4, 5, 6), (1, 2, 3)

示例代码:

class Solution:
    def longestCommonPrefix(self, strs):
        res = ""
        if not strs:
            return ""
        #利用zip(*)函数将每个字符串的字符依次取出生成元组, 元素个数为最短的字符串长度
        for each in zip(*strs):
            #利用集合创建一个无序不重复元素集
            if len(set(each)) == 1: #如果集合元素为1, 则说明此字符是公共的
                res += each[0]
            else:
                return res
        return res

总结

原理上都是逐个取字符进行比较, 如果转成 set 类型除重会简单很多.