leetcode - 5.最长公共前缀

最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。

例如
输入:strs = ["flower","flaw","flight"]
输出:"fl"

解法一

思路

通过字符串比较的思路,以["flower","flaw","flight"]为例,三个字符串的第一个字符和第二个字符都是一样的,在比较第三个字符的时候,a<i<o,所以flaw最小,flower最大,flight排中间,而这里其实只要找最小和最大的公共前缀,因为最小和最大的公共前缀是相等的,那夹中间的必然也相等!否则他就不是排中间了!

涉及知识点:切片、字符串比较、内建函数min、max

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        min_s = min(strs)
        max_s = max(strs)
        for i, num in enumerate(list(min_s)):
            if num != max_s[i]:
                return max_s[:i]
        return min_s
时间复杂度:O(n)
执行用时:32 ms
内存消耗:15.1 MB

解法二

思路

  1. 通过zip函数把["flower","flaw","flight"]对象中的元素打包成一个个元组

  2. 然后使用map+set去重,得到的列表中元素长度为1的就是公共的,把他们加起来就拿到了最长公共前缀

class Solution:
    def longestCommonPrefix(self,strs):
        if strs == "":
            return ""
        s = list(map(set, zip(*strs)))  # s是[{'f'}, {'l'}, {'i', 'a', 'o'}, {'w', 'g'}]
        result = ""
        for i,num in enumerate(s):
            num = list(num)
            if len(num) > 1:
                break
            result += num[0]
        return result
时间复杂度:O(n)
执行用时:32
内存消耗:15

zip在python3中返回的是一个对象,需要使用list()来转换成列表

上一篇:【leetcode】14:最长公共前缀


下一篇:leetcode-14-最长公共前缀(简单)