算法知识点
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。而最长公共子串（要求连续）和最长公共子序列是不同的。
算法题目来源
算法题目描述
给定两个字符串 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 <= 1000
text1 和 text2 仅由小写英文字符组成。做题思路
- 采用dp二维数组，dpi用来表示text1[i]与text2[j]的最长公共子序列长度
- 遍历过程中，如果text1[i]与text2[j]相等时，则dpi = dpi - 1 + 1
- 遍历过程中，如果text1[i]与text2[j]不相等时，，那么dpi = Math.max(dpi,dpi - 1)
- 直到遍历dp数组完成，则dptext1.length()的值，即为我们所求的text1[i]与text2[j]的最长公共子序列长度
Java代码
class Main {
public static void main(String[] args) {
String str1 = "abcde";
String str2 = "ace";
System.out.println("两个字符串的最长公共子序列长度为：" + longestCommonSubsequence(str1, str2));
}
/**
* 最长公共子序列
*
* @Title: lcsSubString
* @Description:
* @author: itbird
* @date 2022年10月21日 下午4:05:01
* @param str1
* @param str2
* @return int 时间复杂度: O(m*n) 空间复杂度: O(m*n)
*/
public static int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() <= 0 || text2 == null
|| text2.length() <= 0) {
return 0;
}
// dp二维数组，dp[i][j]用来表示text1[i]与text2[j]的最长公共子序列长度
int[][] dp = new int[text1.length() + 1][text2.length() + 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] = dp[i - 1][j - 1] + 1;
} else {
// 如果text1[i]与text2[j]不相等时，
// 那么dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j])
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[text1.length()][text2.length()];
}
}问题扩展
如果此时要求输出最长公共子序列的具体字符串呢？有什么办法吗？
我们可以在上面的步骤上，进行如下修改：
- 新增ci二维数组，保持过程状态，保留三个状态
- 1 代表是dpi = dpi - 1 + 1，也就是来源于左上角
- 2 代表是dpi = dpi，也就是来源于左边
- 3 代表是dpi = dpi - 1，也就是来源于上边
- 根据状态为，找到1状态的字符，拼接即为结果
class Main {
public static void main(String[] args) {
String str1 = "abcde";
String str2 = "ace";
System.out.println(
"两个字符串的最长公共子序列长度为：" + longestCommonSubsequence(str1, str2));
}
/**
* 最长公共子序列
*
* @Title: lcsSubString
* @Description:
* @author: itbird
* @date 2022年10月21日 下午4:05:01
* @param str1
* @param str2
* @return int 时间复杂度: O(m*n) 空间复杂度: O(m*n)
*/
public static int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() <= 0 || text2 == null
|| text2.length() <= 0) {
return 0;
}
// dp二维数组，dp[i][j]用来表示text1[i]与text2[j]的最长公共子序列长度
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
int[][] cp = new int[text1.length() + 1][text2.length() + 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] = dp[i - 1][j - 1] + 1;
cp[i][j] = 1;
} else {
// 如果text1[i]与text2[j]不相等时，
// 那么dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j])
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
if (dp[i][j - 1] > dp[i - 1][j]) {
cp[i][j] = 2;
} else {
cp[i][j] = 3;
}
}
}
}
/**
* 遍历，找到公共子序列字符串
*/
for (int i = 0; i < cp.length; i++) {
for (int j = 0; j < cp[0].length; j++) {
if (cp[i][j] == 1) {
System.out.println(text1.charAt(i - 1));
}
}
}
return dp[text1.length()][text2.length()];
}
}运行结果：
