Python 版 LeetCode 刷题笔记 #14 最长公共前缀
Python 版 LeetCode 刷题笔记 #14 最长公共前缀
今天是道简单题，但解题过程中却收获了 zip 的用法，特此一记。
题目
第 14 题 最长公共前缀：
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例：
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。注意:
所有输入只包含小写字母 a-z 。
思路
先说我最直观的思路，先找出列表（即字符串数组）中最短的字符串，接下来遍历整个列表，根据该最短字符串逐位、每次提取所有元素中的首位字符进行拼接，若提取出的字符出现空字符或其它字符，说明公共前缀获取完毕。例如示例中第一个，我们先找到最短的 "flow", 接下来提取列表中所有元素第一位看是否全部为 "f","l","o","w"，当进行对 "o" 的检测时，从 "flight" 中提取到的是"i" 与目标不同，则公共前缀获取完毕，为前两位。
代码
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 先判断个特殊的，空列表直接返回空字符串
if strs==[]:
return ""
# 对列表遍历，获取最短的字符串，赋值给 shortest
l = len(strs)
shortest = ""
len_min = len(strs[0])
for item in strs:
if item=="":
return ""
len_min = min(len_min,len(item))
if len(item)==len_min:
shortest = item
result = ""
# 根据最短的字符串，逐位遍历
for i,c in enumerate(shortest):
# 通过列表推倒式获取所有元素的第 i 位
temp = [x[i] for x in strs if len(x)>i]
# 如果第 i 位所有字符均不为空且全都为相同字符，记录到结果中
if len(temp)==l and set(temp)=={c}:
result+=c
# 如果有空字符、其它字符，结束
else:
return result
# 若正常全部检测完，最终返回结果
return result提交答案
这次运行结果上，用时表现不错。我有点怀疑这个内存消耗，每次都是差不多这么大，也不知怎么去大幅削减。
执行用时 : 44 ms, 在所有 Python3 提交中击败了 50.62% 的用户 内存消耗 :13.8 MB, 在所有 Python3 提交中击败了 6.15% 的用户
优化
上面我写的代码中，通过列表推倒式获取所有元素特定第 i 位的字符，通过生成的结果列表长度与原列表是否相同来判断是否出现空字符；通过将所有字符的列表转化为集合，检查集合中是否只有一个元素（一个元素说明所有字符相同）来判断是否出现其它字符。对于这个设计个人感觉还不错，先去接受其它题解的洗礼再回头看如何优化。
看到个号称 Pythonic 的解法，我给加了些随行注释：
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
res = ""
# 对所有字符串列表进行打包
for tmp in zip(*strs):
# 打包后的每个 tmp 就是对应位置所有字符串的字符，将其转化为集合
tmp_set = set(tmp)
# 如果集合中只有一个元素，即证明全都为同一字符
if len(tmp_set) == 1:
res += tmp[0]
else:
break
return res
#作者：wu_yan_zu
#链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/shui-ping-sao-miao-zhu-xing-jie-shi-python3-by-zhu/这个确实，基本思路是省略掉找最短字符串，直接通过 zip 直接对列表打包：
zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
举个 zip 对列表的例子：
a = [1,2,3,4,5]
b = [11,12,13,14,15]
c = ["a","b","c","d","e"]
x = zip(a,b,c)
print(list(x))它的结果是将每个参数对应的对象元素打包出一个个元组：
[(1, 11, 'a'), (2, 12, 'b'), (3, 13, 'c'), (4, 14, 'd'), (5, 15, 'e')]因为字符串也是可迭代对象，所以这里就通过 *strs 这种列表前加星号（作用是将列表解开，每个元素作为独立参数）来对所有字符串进行打包。
拿示例一来演示下：
strs=["flower","flow","flight"]
x = zip(*strs)
print(list(x))列表 strs 前加星号，将 3 个元素字符串传入 zip() 中，将每个字符串逐位打包出元组，得到结果：
[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]结果中第一个就是所有字符串的首位字符组成的元组，之后是按位来生成的。又由于 zip 是按最短的参数对象来进行分配，所以结果长度也与最短的字符串相对应。
突然觉得这 zip 的用法完美契合题目啊！这么看下来，我们原先代码中找最短字符可以省略，略显麻烦的逐位字符也可以通过 zip 生成的元组来取代了。
该代码的运行结果和之前的表现差不多：
执行用时 : 44 ms, 在所有 Python3 提交中击败了 50.62% 的用户 内存消耗 :13.8 MB, 在所有 Python3 提交中击败了 6.15% 的用户
现在再回头看自己代码进行优化的话，砍掉找最短字符串，应用 zip……改还不如直接从头按推荐题解这样重写呢。
结论
第 14 题，简单难度，最初写完看题解评论时，不限定编程语言，官方题解给出了诸多解法：水平扫描、二分查找、分治等诸多算法，但当选定 python3 标签后，就基本都是文中提到的这方法了。关注点也由不同算法转移到了 zip 的应用，也算小有收获吧。
确实，像类似 zip()、*列表 这些，可能知道它们是怎么回事，没有应用场景还挺难往这联想的，多用才是王道。
腾讯云开发者
