编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""
这是一个简单题（？？？对我来说，可能并不简单），实际做的时候发现，根本不会，自己的暴力解超出了时间限制，做了许久，只能看解析。
!!!看解析我都看不大懂，哭，这就是简单题的威力吗？图解很好懂，但具体实现就比较费解。今天把答案贴上来，加上自己的注释理解。
一、首先是官方的横向扫描法
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
prefix, count = strs[0], len(strs)#先将第一个元素设置为公共前缀
for i in range(1, count):#从第二个元素开始遍历，更新其公共前缀
prefix = self.lcp(prefix, strs[i])
if not prefix:
break
return prefix
def lcp(self, str1, str2):
length, index = min(len(str1), len(str2)), 0 #公共前缀长度一定小于所有字符串长度，所以取最小
while index < length and str1[index] == str2[index]:
index += 1
return str1[:index]#返回相同前缀项
时间复杂度O（mn），m是字符串平均长度，n为字符串数目。
空间复杂度O（1）
二、纵向扫描法
类似横向扫描法，将每一列开始比较，若一列中有不同元素，则公共前缀为前n列元素。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
length, count = len(strs[0]), len(strs)#将第一项设为默认前缀
for i in range(length):
c = strs[0][i]
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):#比较每一列元素
return strs[0][:i]
return strs[0]
时间复杂度O（mn），m是字符串平均长度，n为字符串数目。
空间复杂度O（1）
官方还有两个方法：分治法和二分查找法，图解也是比较好理解，但实际实现对我目前来说还不太容易。这里不详细述说，这里再介绍两种其他方法。
一个是利用zip() 函数：
zip()函数相当于压缩去重的作用，zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。相关链接zip()函数使用
太妙了！
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
res = ""
for tmp in zip(*strs):
tmp_set = set(tmp)
if len(tmp_set) == 1:#一个元素证明是公共元素
res += tmp[0]
else:
break
return res
时间复杂度有内置库不好判断，python就是这点不好分析，虽然库从另一角度是他的优点（奈何Java内容太多，我想学Java来不及）
另一个是利用ascll码，贴一下大佬的回答：利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀
def longestCommonPrefix(self, strs):
if not strs: return ""
s1 = min(strs)
s2 = max(strs)
for i,x in enumerate(s1):
if x != s2[i]:
return s2[:i]
return s1
另，大佬没解释的一点是ascll码是从前往后按位比较的，所以不存在字符串越长越大。
