LeetCode、1143. 最长公共子序列【中等，二维DP】

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

---

LeetCode、1143. 最长公共子序列【中等，二维DP】

题目链接与分类

题目内容：给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

题目链接：

• 牛客：最长公共子序列(二)
• leetcode：LeetCode、1143. 最长公共子序列

分类：动态规划/二维DP

---

思路

2022年暑假学习思路及题解

思路：dp+递归。①nxn遍历，来进行计算dp中每个格子的可连接

示例：把思路理清楚了就ok。

"1A2C3D4B56", "B1D23A456A"
结果：123456

下图中每个格子的左边是dp的值，右边红色的是方向数组b的值。左下角包含有思路解决：

复杂度分析：

• 空间复杂度：O(n²)
• 时间复杂度：O(n²)

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个的最长公共子序列数量。对于当前元素i，j来说，若是当前选不选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—校园工作室管理系统(含前后台，SpringBoot+Vue)：博主个人独立项目，包含详细部署上线视频，已开源
• 学习与生活-专栏：可以了解博主的学习历程
• 算法专栏：算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻，🍅文末获取开发资源及更多资源博客获取🍅

---

整理者：长路 时间：2024.2.7