网站建设相关网站,php网站方案,婴儿网站建设住栏目,环球贸易网1143. 最长公共子序列
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些…1143. 最长公共子序列
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1 输入text1 “abcde”, text2 “ace” 输出3 解释最长公共子序列是 “ace” 它的长度为 3 。 示例 2 输入text1 “abc”, text2 “abc” 输出3 解释最长公共子序列是 “abc” 它的长度为 3 。 示例 3 输入text1 “abc”, text2 “def” 输出0 解释两个字符串没有公共子序列返回 0 。 提示
1 text1.length, text2.length 1000text1 和 text2 仅由小写英文字符组成。
思路(动态规划)
对于两个子序列 S1S1S1 和 S2S2S2找出它们最长的公共子序列。
定义一个二维数组 dp 用来存储最长公共子序列的长度其中 dp[i][j] 表示 S1S1S1 的前 i 个字符与 S2S2S2 的前 j 个字符最长公共子序列的长度。考虑 S1iS1_iS1i与 S2jS2_jS2j 值是否相等分为两种情况
当 S1iS2jS1_i S2_jS1iS2j 时那么就能在 S1S1S1 的前 i -1 个字符与 S2S2S2 的前 j -1 个字符最长公共子序列的基础上再加上 S1iS1_iS1i 这个值最长公共子序列长度加 1即 dp[i][j] dp[i-1][j-1] 1。当 S1i!S2jS1_i ! S2_jS1i!S2j 时此时最长公共子序列为 S1S1S1的前 i -1 个字符和 S2 的前 j 个字符最长公共子序列或者 S1S1S1 的前 i 个字符和 S2S2S2 的前 j -1 个字符最长公共子序列取它们的最大者即 dp[i][j] max{ dp[i-1][j], dp[i][j-1] }。
综上最长公共子序列的 状态转移方程 为
dp[i][j]{dp[i−1][j−1]1S1iS2jmax(dp[i−1][j],dp[i][j−1])S1iS2jd p[i][j]\left\{\begin{array}{rr} d p[i-1][j-1]1 S 1_{i}S 2_{j} \\ \max (d p[i-1][j], d p[i][j-1]) S 1_{i}S 2_{j} \end{array}\right.dp[i][j]{dp[i−1][j−1]1max(dp[i−1][j],dp[i][j−1])S1iS2jS1iS2j
对于长度为 m 的序列 S1 和长度为 n 的序列 S2dp[m][n] 就是序列 S1 和序列 S2 的最长公共子序列长度。
与最长递增子序列 相比最长公共子序列有以下不同点
针对的是两个序列求它们的最长公共子序列。在最长递增子序列中dp[i] 表示以 SiS_iSi 为结尾的最长递增子序列长度子序列必须包含 SiS_iSi 在最长公共子序列中dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度不一定包含 S1iS1_iS1i 和 S2jS2_jS2j。在求最终解时最长公共子序列中 dp[m][n] 就是最终解而最长递增子序列中 dp[n] 不是最终解因为以 SnS_nSn 为结尾的最长递增子序列不一定是整个序列最长递增子序列需要遍历一遍 dp 数组找到最大者。
代码(Java)
public class LongestCommonSubsequence {public static void main(String[] args) {// TODO Auto-generated method stubString text1 abcde;String text2 ace;System.out.println(longestCommonSubsequence(text1,text2));}public static int longestCommonSubsequence(String text1, String text2) {int m text1.length();int n text2.length();int[][] dp new int[m 1][n 1];for(int i 1; i m; i) {for(int j 1; j n; j) {if(text1.charAt(i - 1) text2.charAt(j - 1)) {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[m][n];}
}运行结果 复杂度分析
时间复杂度O(mn)O(mn)O(mn)需要遍历两个字符串。空间复杂度O(mn)O(mn)O(mn)需要m*n的二维数组。
注仅供学习参考
题目来源力扣。
