编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:""
解释:输入不存在公共前缀。
示例1:
class Solution: def longestCommonPrefix(self, s: List[str]) -> str: if not s: return "" s.sort() n = len(s) a = s[0] b = s[n-1] res = "" for i in range(len(a)): if i < len(b) and a[i] == b[i]: res += a[i] else: break return res
调试:
class Solution: def longestCommonPrefix(self, strs): ans = '' # print(*strs) for i in list(zip(*strs)): if len(set(i)) == 1: ans += i[0] else: break return ans if __name__ == '__main__': s = Solution() result_list = s.longestCommonPrefix(["flower","flow","flight"]) print(result_list)
(1) zip()函数的意思:
– zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。
>>>a = [1,2,3] >>> b = [4,5,6] >>> c = [4,5,6,7,8] >>> zipped = zip(a,b) # 打包为元组的列表 [(1, 4), (2, 5), (3, 6)] >>> zip(a,c) # 元素个数与最短的列表一致 [(1, 4), (2, 5), (3, 6)]
(2) zip()函数中带“ * ”号的意思:
– 如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表。
>>> zip(*zipped) # 与 zip 相反,*zipped 可理解为解压,返回二维矩阵式 [(1, 2, 3), (4, 5, 6)]
(3)set()函数:
–set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。
x = set('runoob') print(x) >>{'b', 'r', 'n', 'u', 'o'} # 重复的o,只留下一个
在本例中,
class Solution: def longestCommonPrefix(self, strs): ans = '' print('list(zip(*strs)):',list(zip(*strs))) for i in list(zip(*strs)): print('i:',i) print(set(i)) print(len(set(i))) if len(set(i)) == 1: ans += i[0] else: break return ans if __name__ == '__main__': s = Solution() result_list = s.longestCommonPrefix(["flower","flow","flight"]) print('result_list:',result_list)
输出为:
list(zip(*strs)): [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')] i: ('f', 'f', 'f') {'f'} 1 i: ('l', 'l', 'l') {'l'} 1 i: ('o', 'o', 'i') {'i', 'o'} 2 result_list: fl
再一个:关于list(zip(*strs))和 list(zip(strs))
x = list(zip('runoob')) print(x) >>[('r',), ('u',), ('n',), ('o',), ('o',), ('b',)]
x = list(zip(*["flower","flow","flight"])) print(x) >>[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
x = list(zip(["flower","flow","flight"])) print(x) >>[('flower',), ('flow',), ('flight',)]