最长公共子序列力扣题

2024-03-25 22:52
文章标签 最长 序列 公共 力扣题

本文主要是介绍最长公共子序列力扣题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划。
美团暑期面试题,没做过,不会啊。

这个问题的目标是找出两个字符串text1text2的最长公共子序列的长度。

动态规划数组的初始化

首先,代码初始化了一个动态规划(DP)数组dp,其维度为(m + 1) x (n + 1),其中mn分别是text1text2的长度。这个DP数组用于存储子问题的解,dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。初始化时,所有元素都设置为0。

dp = [[0] * (n + 1) for _ in range(m + 1)]

填充DP数组

接下来,代码通过两层循环遍历这个DP数组,外层循环变量i从1到m,内层循环变量j从1到n。这里,ij分别代表text1text2当前考虑的字符位置。

for i in range(1, m + 1):for j in range(1, n + 1):

对于每一对(i, j),我们比较text1[i - 1]text2[j - 1](即当前考虑的字符)。

  • 如果这两个字符相等,说明我们找到了一个公共子序列中的字符,所以dp[i][j]应该是这个字符加上之前的最长公共子序列的长度,即dp[i - 1][j - 1] + 1
if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果这两个字符不相等,那么当前的最长公共子序列的长度将是两种情况中的较大值:一种是不包含text1[i - 1]时的最长公共子序列长度dp[i - 1][j],另一种是不包含text2[j - 1]时的最长公共子序列长度dp[i][j - 1]
else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

返回结果

最后,dp[m][n]包含了整个问题的解,即text1text2的最长公共子序列的长度。

return dp[m][n]

这个动态规划解法的核心在于逐步构建解的过程,它利用了子问题的解来解决更大的问题,直到解决了整个问题。通过填充DP数组,我们可以高效地找到两个字符串的最长公共子序列的长度。

整合:

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 计算字符串长度m, n = len(text1), len(text2)# 初始化序列长度数组dp = [[0] * (n + 1) for _ in range(m + 1)]# 双重遍历for i in range(1, m+1):for j in range(1, n+1):# 如果当前字符相等,那最长公共子序列就应该是之前的加上现在的一个if text1[i-1] == text2[j-1]:dp[i][j] = dp[i - 1][j - 1] + 1# 否则,应该是那么当前的最长公共子序列的长度将是两种情况中的较大值# 一种是不含第一个字符串的当前字符# 一种是不含第二个字符串的当前字符else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最终结果return dp[m][n]

这篇关于最长公共子序列力扣题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/846505

相关文章

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the