【每日力扣Leetcode】14-查找字符串数组中的最长公共前缀

力扣题库14，查找字符串数组中的最长公共前缀。

题目链接点这里。

文章目录

题目描述解题思路初始答案改进答案注意事项

题目描述

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

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

示例 1:

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

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

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

解题思路

一看这道题就会涉及到遍历操作。做了几道力扣题目之后发现，涉及到遍历或者是递归这种非常耗时的操作，一定要尽量思考如何能够提前进行结果的返回，最典型的就是题目110《【每日力扣Leetcode】110-判断一个二叉树是不是平衡二叉树》。

这里我想的是如果在遍历的过程中已经确定公共前缀不存在了就不用继续遍历了，于是可以从下标0开始，每比较一次就更新一次当前的前缀，然后用前缀去和下一个元素比较。一旦前缀长度变为零就表明没有公共前缀，退出循环。

循环体中就是比较两个字符串的公共前缀，能想到的就是从下标0开始遍历，逐个比较两字符串的每个元素是否相等。

初始答案

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: def strPrefix(str1: str,str2: str) -> str: len1 = len(str1) len2 = len(str2) if len1 == 0 or len2 == 0: return "" for i in range(min(len1,len2)): if str1[i] == str2[i]: i+=1 else: return str1[:i] return str1[:i] if len(strs)==0: return "" if len(strs)==1: return strs[0] prefix = strs[0] for i in range(1,len(strs)): prefix=strPrefix(prefix,strs[i]) if len(prefix)==0: return prefix return prefix

最坏情况下，假设最短字符串的长度为m，字符串个数为n，每个字符串都遍历一遍，时间复杂度为O(mn)。提交之后执行用时: 48 ms，超过了31%的提交。

改进答案

初始答案是用的横向对比，答案中还有一个纵向对比，其中很巧妙的运用了python中set数据不会有重复元素的特性来进行查重。

从下标0开始，获取所有字符串的单个字符放进一个set中，如果set的长度为1说明所有元素都相同。不过这里需要注意的是，假如其中有个字符串已经不能获取下个字符了就会报错，所以要用下try结构。

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs)==0: return "" if strs[0]=="": return "" for i in range(len(strs[0])): try: temp=set([item[i] for item in strs]) except Exception as e: return strs[0][:i] if not len(temp)==1: return strs[0][:i] return strs[0]

这里利用了列表生成器来将所有字符串的单个字符放进一个list中，然后转为set。如果这一步操作报错说明有字符串到头了，就不用再继续往下了，直接返回当前的前缀即可。

时间复杂度的话其实和上面一样也是O(mn)，但是提交以后发现执行用时: 40 ms，击败了76%的提交，看来这个python自带的列表生成器还是挺省时的。

注意事项

从这个题目可以看出来python的一些内置方法都是经过优化的，又想到之前在学KMP算法的时候其实就是为了实现python中字符串的find方法，但是据说find方法也是经过优化的，这里我还没有测试过。不过不考虑算法实现的话，能够使用内置方法就尽量去使用。

网上还有些花里胡哨的思路，二分法啥的，除了秀操作感觉没有必要。

我是T型人小付，一位坚持终身学习的互联网从业者。喜欢我的博客欢迎在csdn上关注我，如果有问题欢迎在底下的评论区交流，谢谢。