1143. 最长公共子序列(LeetCode)_Lucas-hao的博客-程序员秘密

技术标签: 算法  字符串  Leetcode刷题笔记  leetcode  数据结构  

题目描述

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列 的长度。如果不存在公共子序列 ,返回 0 。

一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace” ,它的长度为 3 。
示例 2:

输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc” ,它的长度为 3 。
示例 3:

输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0 。

提示:

  • 1 <= text1.length, text2.length <= 1000
  • text1text2 仅由小写英文字符组成。

题解

经典的动态规划。dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列个数。当我们移动到(i, j)这个位置的时候,分为以下两种情况:

  • text1[i] == text2[j]。此时dp[i][j]=dp[i-1][j-1]+1;
  • text1[i] != text2[j]。此时dp[i][j]=max(dp[i-1][j], dp[i][j-1])
/* 动态规划 */
int longestCommonSubsequence(char * text1, char * text2){
    
    int len1 = strlen(text1), len2 = strlen(text2);
    int dp[1000][1000];
    int i, j;
    for(i = 0; i <= len1; i++) dp[i][0] = 0;
    for(i = 0; i <= len2; i++) dp[0][i] = 0;
    for (i = 1; i <= len1; i++) {
    
        for (j = 1; j <= len2; j++) {
    
            if (text1[i-1] == text2[j-1]) {
    
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
    
                dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }
    return dp[len1][len2];
}

注意

  • 在代码中尽量不要使用分配内存的方法,内存消耗明显增加。
  • 调用函数也会增加运行的时间,如果定义max函数,运行时间会变长。
  • 初始化dp表的时候,可以简单通过int dp[1000][1000] = {0};来进行初始化,但是这样会初始化一些不需要初始化的位置,运行时间会增加。所以只需要通过遍历初始化第一行和第一列即可。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45951701/article/details/115413229

智能推荐

使用acegi进行身份验证_zhu473105308的博客-程序员秘密

使用acegi进行身份验证  http://qingfengxia2.blog.163.com/blog/static/25478407200841394238471/2008-05-13 09:42:38|  分类: spring资料 |  标签: |字号大中小 订

2021-5-22【考试中常见的典型程序设计题目】【】_Eternity_GQM的博客-程序员秘密_程序设计考试题目

一、基础知识:1. 普通变量(整型、单精度实型、双精度实型、字符型)的定义、数组的定义、指针变量的定义、结构体变量的定义2. 以上变量的输入输出方法。二、考试中常见的典型程序设计题目(一)顺序结构程序设计1.按照给出的公式求三角形的面积、梯形面积,华氏温度转换为摄氏温度#include&lt;stdio.h&gt;#include&lt;math.h&gt;//知道三角形三边长,求面积//海伦公式 int main(){ double a,b,c;//定义变量三边长 double

linux下dns本地缓存,linux下安装dns本地缓存_付子花的博客-程序员秘密

linux的版本是gentoo写爬虫不用dns缓存很容易就Error:6 - Couldn't resolve host 'rss.news.yahoo.com'装一个缓存也很简单 摘抄如下 赞美D前辈http://electrostorm.net/archive/2007/10/enabling-dns-cache-dnsmasq-gentoo""""# emerge -av dnsmasqTh...

CCNA2.0笔记_ipv6的EIGRP_weixin_33757911的博客-程序员秘密

IPv6的eigrp特征:  邻居发现  增量更新 快速收敛 负载均衡 三个表  -邻居表  -拓扑表  -路由表配置ipv6的eigrpRouter(config)#ipv6 unicast-routing //启用ipv6路由转发功能Router(config)#ipv6 router eigrp 1 //配置AS号为1Route...

管道-阻塞与非阻塞_zuozi123456的博客-程序员秘密_管道阻塞和非阻塞

非阻塞的管道和FIFO管道和FIFO都可以设置非阻塞。它们两者都可以在打开之后通过fcntl函数设置O_NONBLOCK标志来enable。一般而言,我们都是先使用F_GETFL来获取当前文件状态标志,将它与O_NONBLOCK按位或之后,再通过F_SETFL来设置新的文件状态标志。int flags = fcntl(fd, F_GETFL, 0);if (flags < 0) { E

使用Weditor(uiautomator2)替换uiautomatorviewer抓取Android控件_yinshuilan的博客-程序员秘密_weditor获取某个范围内的控件

问题描述:最近遇到一个问题,uiautomatorviewer.bat工具没法抓取android8以上的手机元素。推荐一个比较好用的工具来替换uiautomatorviewer。参考的原文地址:https://testerhome.com/topics/11357。优点:weditor不仅可以获取android层次结构,还可以与手机的点击、sendkey交互,还能自动生成事件代码,是A..._1671465600

随便推点

Nosql Mongodb之旅(13)—MongoDB 导入导出_孙飞 Sunface的博客-程序员秘密

内容比较简单,依葫芦画瓢。    先讲导入,导入分为两种:json数据导入以及csv数据导入。    导入json数据    我们先将表user删除掉,以便演示效果:[plain] view plaincopy> db.user.drop();   true   > show collections;   system.ind

log4j2自定义配置文件位置和文件名(附log4j2.xml配置实例)转载’https://blog.csdn.net/wengengeng/article/details/53674160_weixin_42128488的博客-程序员秘密_log4j2配置工程名称

前言我们使用log4j2一般做法是将log4j2.xml文件放在资源文件夹根目录。对于有强迫症的开发者来说,我更喜欢在资源文件夹下新建包或文件夹,然后把配置文件放在里面。本博客将介绍如何自定义log4j2.xml文件的位置和文件名。&amp;lt;!-- 系统日志配置监听器 --&amp;gt; &amp;lt;listener&amp;gt; &amp;lt;listener-class&amp;gt;edu.exam...

MXNet之gluonCV中关于路径的操作_高精度计算机视觉的博客-程序员秘密

举例:OS和SYS中的路径操作importosas_osimportreas_reimportsysas_sys在程序中,使用ifprogisNone:prog=_os.path.basename(_sys.argv[0])这里,_sys.argv[0]就是你运行的主程序(假设名字叫test.py吧)的路径,如 ‘d:\\mxNet\\gluon_cv_tests\\ADE20K\\test.py'prog就是得到的文字名称,这里是't...

怎么把qlv格式转化成mp3格式 格式工厂_打开官网的博客-程序员秘密_怎么把qlv文件转换mp3

1、搜索: 小白兔视频格式在线转换2、上传你的视频(腾讯qlv,爱奇艺qsv、优酷kux)都可以。3、转换好后,我们把转换的视频下载到电脑里,就可以看到视频已经是MP4格式了。...

数论--HDU1262 寻找素数对【素数】_caorui_blog的博客-程序员秘密

寻找素数对Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14663    Accepted Submission(s): 7357Problem Description哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序...

善用Wink,将电脑操作录屏为flash_weixin_34329187的博客-程序员秘密

http://blog.sina.com.cn/s/blog_46dac66f010009kv.html【摘要】:Wink 是一款非常优秀的免费录屏软件,尤其适合制作计算机操作教程。它在国外备受推崇,但国内应用很少。它免费、小巧(3MB)、可同期或事后加入声音、可加入暂停及跳转按钮、添加注释,并且生成的 flash 文件比其他软件小很多。本文一方面介绍wink的基本功能,另一方面分享笔者在wi...

推荐文章

热门文章

相关标签