[Leetcode] 0014. 最长公共前缀

这篇具有很好参考价值的文章主要介绍了[Leetcode] 0014. 最长公共前缀。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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方法,更新公共前缀,最后公共前缀越来越短。

[Leetcode] 0014. 最长公共前缀

复杂度分析:

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

空间复杂度:\(O(1)\)。使用的额外空间复杂度为常数。文章来源地址https://www.toymoban.com/news/detail-497179.html

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);
   }
};

解法二

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

[Leetcode] 0014. 最长公共前缀

复杂度分析:

时间复杂度:\(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];
   }
};

到了这里,关于[Leetcode] 0014. 最长公共前缀的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 探秘力扣之谜:如何轻松解决最长公共前缀问题?

    本篇博客我会讲解力扣中的“14. 最长公共前缀”这道题,这是题目链接。 先来审题: 以下是几个输出示例: 提示: 这道题的思路其实并不难,也是一些字符串的常规操作的结合。大家可以先思考一下,再来听我讲解。 思路是这样的:外层循环遍历第一个字符串的每一个字

    2024年02月03日
    浏览(55)
  • Leetcode1143. 最长公共子序列

    解题思路 求两个数组或者字符串的最长公共子序列问题,肯定是要用动态规划的。下面的题解并不难,你肯定能看懂。 首先,区分两个概念:子序列可以是不连续的;子数组(子字符串)需要是连续的; 另外,动态规划也是有套路的:单个数组或者字符串要用动态规划时,

    2024年01月25日
    浏览(45)
  • leetcode1143. 最长公共子序列-动态规划(java)

    leetcode1143. 最长公共子序列 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-common-subsequence 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串: 它是由原字

    2024年01月19日
    浏览(44)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • 【LeetCode】1143.最长公共子序列(闫氏dp可视化无分析)

      推荐一下这道题的可视化过程 最长公共子序列 - 动态规划 Lngest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili  

    2024年02月15日
    浏览(46)
  • LeetCode刷题 | 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和

    给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后

    2024年02月12日
    浏览(44)
  • 最长公共子序列和最长公共子串

    最长公共子序列 题目描述 给出1,2,…, n 的两个排列P 1 和 P 2 ,求它们的最长公共子序列。 输入格式 第一行是一个数 n 。 接下来两行,每行为 n 个数,为自然数1,2,…, n 的一个排列。 输出格式 一个数,即最长公共子序列的长度。 题目分析 第一阶段定义dp数组 (1)考虑规模

    2024年02月19日
    浏览(39)
  • 【算法训练-字符串 三】最长公共子串、最长公共子序列

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【】,使用【】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两个地方都出现过才做

    2024年02月09日
    浏览(40)
  • 最长公共子序列(详细代码 注释 分析 以及求出最长公共子序列内容方法)

    文章有些长,希望能够耐心看完,并且对你有帮助,文章是自己看了书之后,总结的,如果有什么错误的地方,欢迎指出。 一些基本的概念: 子序列: 原序列中删除若干个元素得到的序列,即原序列中可以不连续的一段 子串: 原序列中任意个连续的序列元素组成的序列,

    2023年04月15日
    浏览(51)
  • 最长重复子数组,最大子序和,最长公共子序列

    欢迎批评指正!

    2024年04月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包