题目描述
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
样例
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 .
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
算法1
(动态规划) $O(n^2)$
我们要在test1 的test1(0 : i) 范围内找到与test2 在test2(0 : j) 范围内的最长公共字符串长度。
状态定义:
dp[i][j]: 从test1 的0 ~ i范围内与test2 的0 ~ j 范围内的最长公共子序列的长度。换句话说就是找到以text1[i] 字符结尾 和text2[j] 字符结尾的字符串,然后找到其中最长的子序列长度。
状态计算:
当test1(i) == test2(j) 时,说明此时找到test1 中的i 字符与test2 中的j 字符相等,为公共字符。那么我们就应该尝试去找以test1(i-1) 字符结尾和以test2(j-1) 字符结尾的最长公共子序列的长度 ,即dp[i-1][j-1] ,然后 + 1.
当test1(i) != test2(j) 时,那只能够找test1(i - 1) 与test2(j) 或者test(i) 与test2(j - 1) 时最长公共字符串的长度.因为子序列在字符串中是不需要连续的,所以我们只要找到dp[i-1][j] 和dp[i][j-1] 中的最大值来作为当前以text1[i] 字符结尾和text2[j] 字符结尾的字符中的最大值即可。
初始状态:
当test1 字符串长度为0 时,那么在test2 中是不可能找到公共子序列的,所以dp[0][j] = 0;
当test2 字符串长度为0 时,那么在test1 中是不可能找到公共子序列的,所以dp[i][0] = 0;
因为我们需要腾出一个位置来记录test1,test2 字符串长度为0 的情况,所以i 与j 的大小都是test1,test2 的长度 + 1.
时间复杂度
O(N * M)
参考文献
Java 代码
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length(),m = text2.length();
int[][] dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; 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[n][m];
}