电力建设工程最好的网站,黄冈市建设银行网站,电商运营数据六大指标,智慧团建系统官方网站题目描述
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xf…题目描述
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 思路
这是一道经典的动态规划题我们首先来看状态表示
状态表示dp[i][j]表示字符串text1的[1,i]区间和字符串text2的[1,j]区间的最长公共子序列长度下标从1开始
状态计算
1、若text1[i] text2[j] 也就是说两个字符串的最后一位相等那么问题就转化成了字符串text1的[1,j-1]区间和字符串text2的[1,j-1]区间的最长公共子序列长度再加上一即dp[i][j] dp[i - 1][j - 1] 1。下标从1开始
2、若text1[i] ! text2[j] 也就是说两个字符串的最后一位不相等那么问题就转化成了字符串text1的[1,j-1]区间和字符串text2的[1,j-1]区间的为什么这么说呢因为有以下三种情况最后一种情况会被排除因为对于case1和case2两种情况来说最终结果都大于等于case3的结果text1[i…]text1[i1…]
case1text1[i]不在子序列中如text1: abc text2 bc i0
case2text2[j]不在子序列中如text1: bc text2 abc j0
case3text1[i]和text2[j]不在序列中如text1: abc text2: dbc ij0
状态转移方程
case1text1[i] text2[j] dp[i][j] 1 dp[i - 1][j - 1]
case2text1[i] ! text2[j] dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1])
代码如下 public int longestCommonSubsequence(String text1, String text2) {int m text1.length(), n text2.length();int[][] dp new int[m 1][n 1];for(int i 1;i dp.length;i){for(int j 1;j dp[0].length;j){if(text1.charAt(i - 1) text2.charAt(j - 1)){dp[i][j] 1 dp[i - 1][j - 1];}else{dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
