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]更短的元素,提前结束。

发表评论

电子邮件地址不会被公开。