leetcode[14]-最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”，所有输入只包含小写字母 a-z。

python代码

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        #**********method-1**********
        # r_str = ''
        # for _ ,i in enumerate(zip(*strs)):
        #     if len(set(i))>1:
        #         return r_str
        #     else:
        #         r_str += i[0]
        # return r_str

        #**********method-2**********
        r_str=''
        if len(strs)==0:
            return r_str
        max_len = len(strs[0])
        for i in xrange(max_len):
            temp_str = strs[0][i]
            for item in strs:
                if i>=len(item) or temp_str!=item[i]:
                    return r_str
            r_str+=temp_str
        return r_str

这道题我的理解是属于考察编程能力的题，思路不难。我这实现了两种方法，其中第一种是用了特殊的函数，比较凑巧；第二种比较常规。

r_str = ''
for _ ,i in enumerate(zip(*strs)):
    if len(set(i))>1:
        return r_str
    else:
        r_str += i[0]
return r_str

这是第一种方法，使用了zip()和set()函数，其中zip(*list)表示将list中的每个元素拆分开，对应位置形成一个元组，并且按照最短元素的长度对其它元组进行截断，然后整个元组再形成列表，set()则正好去除给定元组中的重复值。

strs= ['flower','flow','flat']
zip(*strs):
    [('f','f','f'),
    ('l','l','l'),
    ('o','o','a'),
    ('w','w','t')]

item = strs[0]
item:
    ('f')

使用zip()函数很容易看出来，当item的长度等于1时，说明还处于公共前缀中，因为所有元素当前位置的元素都相等，只要不等于1，那就说明至少有一个是和其它不一样的，那么公共前缀也就到此为止了。

r_str=''
if len(strs)==0:
    return r_str
max_len = len(strs[0])
for i in xrange(max_len):
    temp_str = strs[0][i]
    for item in strs:
        if i>=len(item) or temp_str!=item[i]:
            return r_str
    r_str+=temp_str

第二种方法比较常规，首先考虑特殊情况，当输出的列表为空时，返回空列表。取第一个元素的长度为遍历范围，为什么？这样想，剩下的元素长度要么大于它，要么小于它，大于的就不考虑了，因为公共前缀最长是最短元素的长度。所以我们现在只要每遍历到一个元素就判断是不是它的最后一位，若是就直接结束，反之则继续。第一次取strs[0]的第一位字符，然后遍历剩余元素的第一位，只要遇到不相同的就退出u，如果都一样，则读取strs[0]的第二位字符，继续进行判断，直到遇到不相同的，或者strs[0]遍历完了，或者遇到了比strs[0]更短的元素，提前结束。