苏州网站建设相关技术,怎么创造软件app,自贡建设能源开发有限公司网站,中国邮政做特产的网站文章目录 前言LeetCode、1143. 最长公共子序列【中等#xff0c;二维DP】题目链接与分类思路2022年暑假学习思路及题解二维DP解决 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博客专家、Java领域优质创作者#xff0c;博客之星、阿里云平台优质作者… 文章目录 前言LeetCode、1143. 最长公共子序列【中等二维DP】题目链接与分类思路2022年暑假学习思路及题解二维DP解决 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、1143. 最长公共子序列【中等二维DP】
题目链接与分类
题目内容给定两个字符串str1和str2输出两个字符串的最长公共子序列。如果最长公共子序列为空则返回-1。目前给出的数据仅仅会存在一个最长的公共子序列
题目链接
牛客最长公共子序列(二)leetcodeLeetCode、1143. 最长公共子序列
分类动态规划/二维DP 思路
2022年暑假学习思路及题解
思路dp递归。①nxn遍历来进行计算dp中每个格子的可连接
示例把思路理清楚了就ok。
1A2C3D4B56, B1D23A456A
结果123456下图中每个格子的左边是dp的值右边红色的是方向数组b的值。左下角包含有思路解决 复杂度分析
空间复杂度O(n2)时间复杂度O(n2)
import java.util.*;public class Solution {private String x;private String y;/*** longest common subsequence* param s1 string字符串 the string* param s2 string字符串 the string* return string字符串*/public String LCS (String s1, String s2) {this.x s1;this.y s2;char[] sArr1 s1.toCharArray();char[] sArr2 s2.toCharArray();int[][] dp new int[sArr1.length 1][sArr2.length 1];int[][] d new int[sArr1.length 1][sArr2.length 1];for (int i 1; i sArr1.length; i) {for (int j 1; j sArr2.length; j) {//比较两个字符if (sArr1[i - 1] sArr2[j - 1]) {//若是相同dp[i][j] dp[i - 1][j - 1] 1;d[i][j] 1;}else {if (dp[i - 1][j] dp[i][j - 1]) {dp[i][j] dp[i - 1][j];d[i][j] 2;}else {dp[i][j] dp[i][j - 1];d[i][j] 3;}}}}String ans ans(s1.length(), s2.length(), d);if (ans.isEmpty()) {return -1;}return ans;}//递归获取最长子序列public String ans(int i, int j, int[][] d) {String res ;if (i 0 || j 0) {return res;}if (d[i][j] 1) {res ans(i - 1,j - 1, d);res x.charAt(i - 1);}else if (d[i][j] 2) {res ans(i - 1,j, d);}else {res ans(i, j - 1, d);}return res;}
}二维DP解决 时间2024.2.7 题目链接1143. 最长公共子序列
思路在本题中是找的最长公共子序列并不是子串此时我们可以从选不选的问题上延申出来。
定义dp(i, j)本身这个值表示第一个字串前i个第二个字串前j个的最长公共子序列数量。对于当前元素ij来说若是当前选不选i或者j又或者是选i和j那么是有四种状态的。
dp(i - 1, j)当前i不选j选即第一个字串前i-1个第二个字串前j个中最长公共子序列数量。
dp(i, j - 1)当前i选j不选即第一个字串前i个第二个字串前j-1个中最长公共子序列数量。
dp(i - 1, j - 1)当前i不选j不选即第一个字串前i-1个第二个字串前j-1个中最长公共子序列数量。
dp(i, j)当前i选j选即第一个字串前i个第二个字串前j个中最长公共子序列数量。递推方程从dp(i, j)定值来看我们是根据第1个子串的第i个字符与第2个子串的第j个字符是否相等来作为条件。
dp(i, j) Math.max(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)); 【ch1[i] ! ch2[j]】
dp(i, j) dp(i - 1, j - 1) 1; 【ch1[i] ch2[j]】题解
复杂度分析时间复杂度O(n*m)空间复杂度O(n*m)
class Solution {public int longestCommonSubsequence(String text1, String text2) {int n text1.length(), m text2.length();int[][] dp new int[n 1][m 1];for (int i 1; i n; i ) {char text1Ch text1.charAt(i - 1);for (int j 1; j m; j ) {char text2Ch text2.charAt(j - 1);//若是两个字符相等if (text1Ch text2Ch) {dp[i][j] dp[i - 1][j - 1] 1;}else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[n][m];}
}资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅在下方专栏
长路-文章目录汇总算法、后端Java、前端、运维技术导航博主所有博客导航索引汇总开源项目Studio-Vue—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取 整理者长路 时间2024.2.7
