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

文章目录

前言
LeetCode、1143. 最长公共子序列【中等，二维DP】
- 题目链接与分类
- 思路
- - 2022年暑假学习思路及题解
  - 二维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];
    }
}