【边学边敲边记】LeetCode005:最长公共前缀
一、写在前面
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 努力 : 终有所获
往期精彩
进学习交流群
扫码加X先生微信进学习交流群