题目
给定两个字符串 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]; }}
复制代码
总结
评论