编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
- show the code:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
ss = list(map(set,zip(*strs)))
res = ''
for i,x in enumerate(ss):
x = list(x)
if len(x) > 1:
break
res += x[0]
return res
- 这个题用python非常好做，不需要用到官方题解中的什么分治，水平扫描等等。
- 首先要明白python中zip函数的作用，下面这个例子很好的说明了其作用：
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b) # 返回一个对象
>>> zipped
<zip object at 0x103abc288>
>>> list(zipped) # list() 转换为列表
[(1, 4), (2, 5), (3, 6)]
>>> list(zip(a,c)) # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> a1, a2 = zip(*zip(a,b)) # 与 zip 相反，zip(*) 可理解为解压，返回二维矩阵式
>>> list(a1)
[1, 2, 3]
>>> list(a2)
[4, 5, 6]
- 直接对strs进行解压，将每个字符按照单个字母展开，如
["flower","flow","flight"]解压成[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]这里注意，以最短的单词为准。 - 然后我们就可以找到规律了：只有当三个单词的同一位置的字母相同时，这个字母才是公共前缀。也就是说上文中的
('f','f','f'),('l','l','l')都是公共前缀，于是最后的结果就是'fl'。 - 具体表现到代码中：先对解压后的结果去重，长度为1则表示三个单词均相同，即是公共前缀，长度大于1则
break跳出循环。
