简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
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%
