题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”,所有输入只包含小写字母 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]
更短的元素,提前结束。