新乡做网站的公司有那些,个人如何建立免费手机网站,poco摄影网,洛阳制作网站公司哪家好题目描述
给定两个字符串 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];}
