解决最长公共前缀问题

解决最长公共前缀问题

最长公共前缀问题

---

前言

学习利用python内置函数zip和set函数解决最长公共前缀问题

一、问题描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
来源：力扣

如图应该可以很好的理解，被框住的部分就是最长公共前缀

二、zip和set函数的解释

1.zip()和zip(*)

官方解释：
zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。
**zip 方法在 Python 2 和 Python 3 中的不同：在 Python 3.x 中为了减少内存，zip() 返回的是一个对象。如需展示列表，需手动 list() 转换。

我的理解：
zip含有两种，其中一种是zip()代表压缩，另一种是zip(* )代表解压
zip()将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。

代码如下（示例）：
strs = ["flower","flow","flight"]
a1=zip(strs)
print(list(a1))
#输出 [('flower',), ('flow',), ('flight',)]
a2=zip(*strs)
print(list(a2))
#输出 [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]

2.set函数

创建一个无序不重复元素的集合 ，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。其返回值为一个新的集合对象。

代码如下（示例）：
x='456789'
y='abcde'
z=('a','a','a','a')
print(set(x))
#输出 {'6', '9', '5', '7', '8', '4'}
print(set(y))
#输出 {'b', 'e', 'c', 'a', 'd'}
print(set(z))
#输出 {'a'} 这个会在解题中用到

三、利用zip和set解决最长公共前缀问题

在方法中，我们初始化了一个空字符串ans，用于存储最长公共前缀。然后我们使用zip(*strs)来将字符串列表中的字符串打包成元组的形式，方便我们逐个比较每个字符串的对应位置的字符。

接下来，我们使用for循环遍历这些打包好的元组。对于每个元组i，我们使用set(i)来将元组中的元素转换为集合，然后检查集合的长度是否为1。如果长度为1，说明当前位置的字符在所有字符串中都是相同的，我们就将这个字符添加到ans中。如果长度不为1，说明当前位置的字符在某个字符串中不同，那么我们就跳出循环，因为最长公共前缀已经结束了。

最后，我们返回ans，即为最长公共前缀。

简而言之，使用zip函数取出每个单词相同位置的字母，转化成集合如果字母相同集合长度为1，如果不同就可以直接返回结果

代码如下（示例）：
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans=""
        for i in list(zip(*strs)):
            if len(set(i))==1:
                ans+=i[0]
            else:
                break
        return ans

---

总结

第一次写文章，略有不足请批评指正