首页 > 其他分享 >[Leetcode] 0014. 最长公共前缀

[Leetcode] 0014. 最长公共前缀

时间:2023-06-21 15:23:41浏览次数:43  
标签:0014 return 前缀 strs 复杂度 公共 字符串 Leetcode

14. 最长公共前缀

点击上方,跳转至Leetcode

题目描述

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

如果不存在公共前缀,返回空字符串 ""

 

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

解法一

横向扫描:写一个longestCommonPrefix方法,用于返回两个字符串的公共前缀
然后再主方法中,先让第一个字符串定为公共前缀,然后依次和后面的字符串执行longestCommonPrefix方法,更新公共前缀,最后公共前缀越来越短。

复杂度分析:

时间复杂度:\(O(mn)\),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度:\(O(1)\)。使用的额外空间复杂度为常数。

Python3

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        prefix,count = strs[0],len(strs)
        for i in range(1,count):
            prefix = self.lcp(prefix,strs[i])
            if not prefix:
                break
        return prefix
    
    def lcp(self,str1,str2):
        length ,index = min(len(str1),len(str2)),0
        while index <length and str1[index] == str2[index]:
            index += 1
        return str1[:index]

C++

class Solution {
public:
   string longestCommonPrefix(vector<string>& strs){
        if(!strs.size())
            return "";
        string prefix = strs[0];
        int count = strs.size();
        for(int i=1;i<count; ++i){
            prefix = longestCommonPrefix(prefix,strs[i]);
            if(!prefix.size())
                break;
        }
        return prefix;
   }

   string longestCommonPrefix(const string &str1,const string &str2){
        int length = min(str1.size(),str2.size());
        int index = 0;
        while(index < length && str1[index] == str2[index])
            ++index;

        return str1.substr(0,index);
   }
};

解法二

纵向扫描:依次遍历每个字符串,更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。

复杂度分析:

时间复杂度:\(O(mn)\),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度:\(O(1)\)。使用的额外空间复杂度为常数。

Python3

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        length,count = len(strs[0]),len(strs)
        for i in range(length):
            c= strs[0][i]
            for j in range(1,count):
                if(i==len(strs[j]) or strs[j][i] !=c):
                    return strs[0][:i]

        return strs[0]

C++

class Solution2 {
public:
   string longestCommonPrefix(vector<string>& strs){
        if(!strs.size())
            return "";
        int length = strs[0].size();
        int count = strs.size();
        for(int i=0;i<length;++i){
            char c = strs[0][i];
            for(int j=1;j<count;++j){
                if(i==strs[j].size() || strs[j][i] !=c){
                    return strs[0].substr(0,i);
                }
            }
        }
        return strs[0];
   }
};

标签:0014,return,前缀,strs,复杂度,公共,字符串,Leetcode
From: https://www.cnblogs.com/yege/p/17496289.html

相关文章

  • [Leetcode] 0020. 有效的括号
    20.有效的括号点击上方,跳转至leetcode题目描述给定一个只包括'(',')','{','}','[',']' 的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例1:输入:s="......
  • [Leetcode] 0724. 寻找数组的中心下标
    724.寻找数组的中心下标点击上方,跳转至leetcode题目描述给你一个整数数组 nums,请计算数组的中心下标。数组中心下标是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端,那么左侧数之和视为0,因为在下标的左侧不存在元素。......
  • [Leetcode] 0728. 自除数
    728.自除数点击上方,跳转至leetcode题目描述自除数 是指可以被它包含的每一位数整除的数。例如,128是一个自除数,因为 128%1==0,128%2==0,128%8==0。自除数不允许包含0。给定两个整数 left 和 right,返回一个列表,列表的元素是范围 [left,right] 内......
  • [Leetcode] 0733. 图像渲染
    733.图像渲染点击上方,跳转至leetcode题目描述有一幅以 mxn 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数sr, sc和newColor。你应该从像素 image[sr][sc] 开始对图像进行上色填充。为了完成上色工作,从......
  • [Leetcode] 0709. 转换成小写字母
    709.转换成小写字母点击上方跳转至Leetcode题目描述给你一个字符串s,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。 示例1:输入:s="Hello"输出:"hello"示例2:输入:s="here"输出:"here"示例3:输入:s="LOVELY"输出:"lovely" 提示:1<=s.l......
  • [Leetcode] 0717. 1 比特与 2 比特字符
    717.1比特与2比特字符点击上方,跳转至leetcode题目描述有两种特殊字符:第一种字符可以用一比特 0表示第二种字符可以用两比特(10 或 11)表示给你一个以0结尾的二进制数组 bits ,如果最后一个字符必须是一个一比特字符,则返回true。 示例 1:输入:bits=[1,......
  • [Leetcode] 0706. 设计哈希映射
    706.设计哈希映射点击跳转至leetcode题目描述不使用任何内建的哈希表库设计一个哈希映射(HashMap)。实现MyHashMap类:MyHashMap()用空映射初始化对象voidput(intkey,intvalue)向HashMap插入一个键值对(key,value)。如果key已经存在于映射中,则更新其对应的值v......
  • [LeetCode] 2090. K Radius Subarray Averages
    Youaregivena 0-indexed array nums of n integers,andaninteger k.The k-radiusaverage forasubarrayof nums centered atsomeindex i withthe radius k istheaverageof all elementsin nums betweentheindices i-k and i+k (i......
  • 每日一题力扣 1262 https://leetcode.cn/problems/greatest-sum-divisible-by-three/
    、 题解这道题目核心就算是要知道如果x%3=2的话,应该要去拿%3=1的数字,这样子才能满足%3=0贪心sum不够%3的时候,就减去余数为1的或者余数为2的需要注意两个余数为1会变成余数为2的,所以可能减去2个余数为1核心代码如下publicintmaxSumDivThreeOther(int[]nums){​  ......
  • vue 学习第17天 CSS学习 ---- 浏览器私有前缀 + css3阶段总结
    浏览器私有前缀是为了兼容老版本的写法,比较新的浏览器无需添加1、私有前缀 2、提倡的写法(私有前缀+属性) 总结:CSS3学习的  五个大方面         ......