Write a function to find the longest common prefix string amongst an array of strings.
Solution1
用第一个元素作为基准，每个元素都与第一个元素的前半部分作compare
算法复杂度为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中的每个元素的每个字符都分别zip在一起，然后透过set的len来看是否字符相等
算法复杂度为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函数用得不够666
- set可以除重，len(set)的用法很妙
