Leetcode— 最长公共前缀（Python3实现）

Leetcode—最长公共前缀

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

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

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:

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

说明:

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

这道题的切入点就是以最短字符串为准，拆分各个字符串，逐个进行比较。

这里我提供了两种解题思路

• 序列解包，将元组转化为集合（集合里的元素是不重复的），判断集合里的元素个数是否为1，如果为1，说明列表里的所有字符串在同一位置拥有相同的字符。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        str2=""
        #序列解包，将字符串拆分为元组形式，['ac','re']==>('a','r'),('c','e')
        for n in zip(*strs):
            #将其集合化，判断是否为1
            list1=set(n)
            if len(list1)==1:
                str2+=n[0]
            else:
                break
        return str2

• 首先对字符串列表进行从小到大的顺序排序，获取最短的字符串，然后拆分最短字符串，将拆分后的最短字符串的各个字符逐个与其它字符串的相同位置的字符进行比较，如果相同，则保存在定义的空列表中，最后判断定义的列表的长度是否为初始输入列表的长度，如果是，说明各个字符串在同一位置有着相同的字符。

def longestCommonPrefix(strs):
    char = ""
    #对列表进行排序
    strs.sort(key=len)
    #处理一些特殊情况
    if len(strs) == 0 or strs[0]=="":
        return char
    #循环次数依据最短字符串来遍历
    for i in range(len(strs[0])):
        list1 = []
        #与strs中的字符串逐个比较
        for j in range(len(strs)):
            if strs[0][i] == strs[j][i]:
                list1.append(strs[0][i])
        #如果次数为列表长度，说明列表中的字符串都含有对应的字符
        if len(list1) == len(strs):
            char += strs[0][i]
        else:
            break
    return char