最长公共前缀
题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
例如
输入:strs = ["flower","flaw","flight"]
输出:"fl"
解法一
思路
通过字符串比较的思路,以["flower","flaw","flight"]为例,三个字符串的第一个字符和第二个字符都是一样的,在比较第三个字符的时候,a<i<o,所以flaw最小,flower最大,flight排中间,而这里其实只要找最小和最大的公共前缀,因为最小和最大的公共前缀是相等的,那夹中间的必然也相等!否则他就不是排中间了!
涉及知识点:切片、字符串比较、内建函数min、max
class Solution:
def longestCommonPrefix(self, strs):
if not strs:
return ""
min_s = min(strs)
max_s = max(strs)
for i, num in enumerate(list(min_s)):
if num != max_s[i]:
return max_s[:i]
return min_s
时间复杂度:O(n)
执行用时:32 ms
内存消耗:15.1 MB
解法二
思路
-
通过zip函数把["flower","flaw","flight"]对象中的元素打包成一个个元组
-
然后使用map+set去重,得到的列表中元素长度为1的就是公共的,把他们加起来就拿到了最长公共前缀
class Solution:
def longestCommonPrefix(self,strs):
if strs == "":
return ""
s = list(map(set, zip(*strs))) # s是[{'f'}, {'l'}, {'i', 'a', 'o'}, {'w', 'g'}]
result = ""
for i,num in enumerate(s):
num = list(num)
if len(num) > 1:
break
result += num[0]
return result
时间复杂度:O(n)
执行用时:32
内存消耗:15
zip在python3中返回的是一个对象,需要使用list()来转换成列表