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

最新推荐文章于 2025-04-01 14:43:20 发布

T型人小付

最新推荐文章于 2025-04-01 14:43:20 发布

阅读量773

点赞数

分类专栏：每日力扣Leetcode

本文链接：https://blog.csdn.net/victor2code/article/details/108393118

版权

每日力扣Leetcode 专栏收录该内容

9 篇文章

订阅专栏

力扣题库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]