Write a function to find the longest common prefix string amongst an array of strings.
Solution1
用第一個(gè)元素作為基準(zhǔn)曲楚，每個(gè)元素都與第一個(gè)元素的前半部分作compare
算法復(fù)雜度為O(n2)
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
elif len(strs) == 1:
return strs[0]
else:
count = 0
while(True):
for i in range(len(strs)):
try:
if not strs[i][count] == strs[0][count]:
return strs[0][:count]
else:
continue
except:
return strs[0][:count]
count += 1
Solution2
將list中的每個(gè)元素的每個(gè)字符都分別zip在一起潦嘶，然后透過set的len來看是否字符相等
算法復(fù)雜度為O(n)
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
for i, v in enumerate(zip(*strs)):
if len(set(v)) > 1:
return strs[0][:i]
return strs[0]
反思
- zip函數(shù)用得不夠666
- set可以除重，len(set)的用法很妙
