写点什么

【LeetCode】最长公共子序列 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 03 日

题目


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


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


例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。


示例 1:


输入:text1 = "abcde", text2 = "ace"


输出:3


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/longest-common-subsequence


代码


public class DayCode {    public static void main(String[] args) {        String text1 = "abcde";        String text2 = "ace";        int ans = new DayCode().longestCommonSubsequence(text1, text2);        System.out.println("ans is " + ans);    }
/** * 时间复杂度 O(m * n) * 空间复杂度 O(m * n) * @param text1 * @param text2 * @return */ public int longestCommonSubsequence(String text1, String text2) { if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) { return 0; }
char[] chars1 = text1.toCharArray(); char[] chars2 = text2.toCharArray(); int m = chars1.length, n = chars2.length; int[][] dp = new int[m][n]; dp[0][0] = (chars1[0] == chars2[0]) ? 1 : 0; for (int i = 1; i < m; i++) { dp[i][0] = chars1[i] == chars2[0] ? 1 : dp[i - 1][0]; } for (int j = 1; j < n; j++) { dp[0][j] = chars1[0] == chars2[j] ? 1 : dp[0][j - 1]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); if (chars1[i] == chars2[j]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1); } } } return dp[m - 1][n - 1]; }}
复制代码


总结

  • 最长公共子序列是一道经典的题目,可以使用动态规划的方法解决。

  • 需要认真分析题目,找出 DP 方程的初始值,然后分析转移关系。当转移的递推公式不好找的时候,可以代入例子,帮助我们简化问题。

  • 坚持每日一题,加油!


发布于: 2021 年 04 月 03 日阅读数: 8
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】最长公共子序列Java题解