【LeetCode】（No.014）最长公共前缀

击上方“Ahab杂货铺”，选择“置顶公众号”

技术分享第一时间送达！

---

NO.14 最长公共前缀

原题：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解题分析：

最长公共前缀指的是字符串数组中所有公共最长的前缀。
如果是空串的话，那么说明前缀就是“”
如果都是以“ ”开头的，那么就是“ ”
然后最长的前缀不会超过最短的字符串，那么可以遍历最短的字符串的长度，依次比较。
第一步：找出长度最短的字符串；
第二步：依次与长度最短的字符串比较。

if strs == []:
return ''
   common = []
flag = 0
  def minimum(s):
m=list(map(len,s))
return s[m.index(min(m))]
temp = minimum(strs)
if temp == '':
return ''
  a = temp[0]
for i in strs:
if i[0] != a:
return ''
  for i in range(len(temp)):
for j in strs:
if temp[i]!=j[i]:
flag = 1
        break
    if flag == 0:
common.append(temp[i])
return ''.join(common)

大神代码：

class Solution:
def longestCommonPrefix(self, strs):
     res = ""
     if len(strs) == 0:
return ""
     for each in zip(*strs):
#zip()函数用于将可迭代对象作为参数，
#将对象中对应的元素打包成一个个元组，
# 然后返回由这些元组组成的列表
       if len(set(each)) == 1:
#利用集合创建一个无序不重复元素集
            res += each[0]
else:
return res
return res

总结：

1.不需要求出最短字符串是哪个，只需要求出最短字符串的长度即可。
2.字符串组的几种情况的判断应更清晰明了。
1）字符串组为空[]
2）公共字符串为空[””]
3)  正常情况

---

微信交流群：

近期推荐阅读：

---

欢迎您的点赞和分享

▲长按关注此公众号