查看原文
其他

【边学边敲边记】LeetCode005:最长公共前缀

老表的第一个一百万 简说Python 2019-05-25

一、写在前面

LeetCode 第四题ATOI算法实现传输门:eetCode004:ATOI算法实现

今天给大家分享的是 LeetCode 数组与字符串 第五题:最长公共前缀,为面试而生,期待你的加入。

二、今日题目

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

示例:

示例 1:

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

示例 2:

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

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

三、 分析

这个题目,第一眼一看,无论是题干还是示例都是---怎么这么简单?错觉,看着的确简单,但是还是有很多难点,比如:strs的长度是不定的;strs里的字符串长度也是不定的,总的来说还是比较简单,我看到题目的第一个想法就是暴力查找,比较,这个方法不是太好,优化了一下思想,主体流程如下:

我的思想

四、解题

  • 我的方法:
    根据上面思想直接敲~
    双重for循环时间复杂度:应该不到O(n^2)

'''
date : 2018.10.11
author : 极简XksA
'''
'''
题目:
最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀,返回空字符串 ""。
    Longest Common Prefix
'''


class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        len0 = len(strs)
        if len0 == 0:
            return ''
        list_len = []
        # 找出最短的字符串长度
        for i in range(len0):
            list_len.append(len(strs[i]))
        list_len.sort()
        # 取出最短的子串
        # 我这里是直接取第一个子串的前min_len
        com_str = strs[0][0:list_len[0]]
        b0 = com_str
        for s in strs:
            for i in range(list_len[0]):
                if s[i] != com_str[i]:
                    # 判断到有不等的地方
                    a0 = s[0:i]
                    if len(b0) >= len(a0):  # 上一个最长公共前缀是否比现在长
                        b0 = a0
        return b0

  • 提交结果

提交结果

测试数据:118组
运行时间:48ms
击败人百分比:92.21%

  • 大牛方法:
    一层for循环时间复杂度:O(n)

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

  • 提交结果

提交结果

测试数据:118组
运行时间:28ms
击败人百分比:95.84%

五、疑惑

没有疑惑,哈哈哈,今天给大家推荐一个算法与数据结构的课程---《算法面试通关40讲》,我已经加入学习了,这份视频课程,加上我之前加入的《算法与数据结构》文章+录音课程配合着,我觉得我应该能有不少收获,购买这个课程除了面试,我还看中了里面的LeetCode高效解题四步法

现在扫描下面二维码,购买课程,可获得以下福利:

  • 1.加我微信(zs820553471),带购买截图,可获得10-20元红包;

  • 2.拉进专门的算法学习交流群,都是热爱算法的读者和大佬朋友。
    算法学习,期待你的加入~

六、结语

今天有个读者问我,我为什么这么优秀,我回答的是“我其实和大家差不多”,真正优秀的是我的坚持,学习就是这样,肯坚持、肯埋头苦干,终有所获我给那个读者了两个建议,这里也分享给大家:

  • 1.自己得坚持学习,找准方向,学python就不要想着java;

  • 2.知识付费,花点钱购买对自己有用的课程(技术、情感、生活等等方面)

希望大家会因为关注了我,而学到一些东西,技术或者生活上,多交流,才能进步。

坚持 and 努力 : 终有所获


END

往期精彩

送书啦,还有两天

爬取《悲伤逆流成河》猫眼信息 | 郭敬明五年电影最动人之作

12306:妈妈再也不用担心我抢不到票了(1)

LeetCode004:字符串转整数 (atoi)

LeetCode003:最长回文子串

进学习交流群

扫码加X先生微信进学习交流群


▼更多精彩推荐,请关注我们▼




感谢支持(1-5元)


    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存