14. 最長(zhǎng)公共前綴
編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴贷祈。
如果不存在公共前綴，返回空字符串 ""顶伞。
例1:
輸入: ["flower","flow","flight"]
輸出: "fl"
例2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴饵撑。
所有輸入只包含小寫字母a-z。
解法1: 取字符串逐一比較
class Solution:
def longestCommonPrefix(self, strs):
# 排除異常情況, 字符串為空或只有1個(gè)
if strs is None or len(strs) == 0:
return ""
elif len(strs) == 1:
return strs[0]
minmun = len(strs[0]) #取出最短字符串的長(zhǎng)度
for each in strs:
if each == "": #如果有空字符串直接返回
return ""
if len(each) < minmun:
minmun = len(each)
res = "" #記錄最長(zhǎng)前綴
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: 逐一比較的簡(jiǎn)化版
依然先算了最短字符串的長(zhǎng)度, 也可以省掉這次計(jì)算直接循環(huán)取公共前綴.
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]) #取最短長(zhǎng)度
end = 0 #記錄公共前綴字符數(shù)
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函數(shù)
zip()函數(shù)用于將可迭代的對(duì)象作為參數(shù)唆貌，將對(duì)象中對(duì)應(yīng)的元素打包成一個(gè)個(gè)元組滑潘，然后返回由這些元組組成的列表。
如果各個(gè)迭代器的元素個(gè)數(shù)不一致锨咙，則返回列表長(zhǎng)度與最短的對(duì)象相同语卤，利用 * 號(hào)操作符，可以將元組解壓為列表。
在 Python 3.x 中為了減少內(nèi)存粹舵，zip() 返回的是一個(gè)對(duì)象.如需展示列表钮孵，需手動(dòng) list() 轉(zhuǎn)換.
Python 3 中 zip() 函數(shù)的用法:
a = [1, 2, 3]
b = [4, 5, 6]
c = [1, 2, 3, 4, 5, 6]
zipped = zip(a, b, c) # zip 對(duì)象<zip object at 0x1074aad88>
list(zipped) # 轉(zhuǎn)成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(*)函數(shù)將每個(gè)字符串的字符依次取出生成元組, 元素個(gè)數(shù)為最短的字符串長(zhǎng)度
for each in zip(*strs):
#利用集合創(chuàng)建一個(gè)無序不重復(fù)元素集
if len(set(each)) == 1: #如果集合元素為1, 則說明此字符是公共的
res += each[0]
else:
return res
return res
總結(jié)
原理上都是逐個(gè)取字符進(jìn)行比較, 如果轉(zhuǎn)成 set 類型除重會(huì)簡(jiǎn)單很多.
