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 类型除重会简单很多.
