算法题目总结 -- 最长公共子序列
问题描述
在两个字符串中，有些字符会一样，可以形成的子序列也有可能相等，因此，长度最长的相等子序列便是两者间的最长公共字序列，其长度可以使用动态规划来求。以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。
最长公共子序列与最长公共子串问题的区别为：
子序列意味着子串可以不必在母串中连续存在
解题思路
求最长子序列长度
两个字符串对应的最长公共子序列不一定唯一，这个程序输出所有的LCS内容。
基本思想是：
代码
/*
* lcs算法
* 子序列意味着子串可以不必在母串中连续存在
* */
public class LongestCommonSubSequence {
/**
*
* @param str1
* @param str2
* @return 最长公共子序列的长度
*/
public static int getLongestCommonSubSequence(String str1, String str2){
int[][] subResult = new int[str1.length()+1][str2.length()+1];
for (int i = 1; i < str1.length()+1; i++) {
for (int j = 1; j < str2.length()+1; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)){
subResult[i][j] = subResult[i-1][j-1] + 1;
}else{
subResult[i][j] = Math.max(subResult[i][j-1], subResult[i-1][j]);
}
}
}
// for (int i = 0; i < str1.length()+1; i++) {
// for (int j = 0; j < str2.length()+1; j++)
// System.out.print(subResult[i][j] + " ");
// System.out.println();
// }
// System.out.println(printLCS(str1, str2, subResult));
HashSet<String> allLcs = new HashSet<>();
printAllLCS(str1, str2, subResult, str1.length(), str2.length(), "", allLcs);
System.out.println(allLcs);
return subResult[str1.length()][str2.length()];
}
/**
*
* @param str1
* @param str2
* @param subResult
* @return 其中一个公共子序列
*/
public static String printLCS(String str1, String str2, int[][] subResult){
String subStr = "";
int i=str1.length(), j=str2.length();
while (i>0 && j>0){
if (str1.charAt(i-1) == str2.charAt(j-1)){
subStr = str1.charAt(i-1) + subStr;
i--;j--;
}else if (subResult[i-1][j] >= subResult[i][j-1]){
i--;
}else {
j--;
}
}
return subStr;
}
public static void printAllLCS(String str1, String str2, int[][] subResult, int i, int j, String comSubStr, HashSet<String> allLcs){
while (i>0 && j>0){
if (str1.charAt(i-1) == str2.charAt(j-1)){
comSubStr = str1.charAt(i-1) + comSubStr;
i--;j--;
}else if (subResult[i-1][j] > subResult[i][j-1]){
i--;
}else if (subResult[i-1][j] < subResult[i][j-1]){
j--;
}else{
printAllLCS(str1, str2, subResult, i-1, j, comSubStr, allLcs);
printAllLCS(str1, str2, subResult, i, j-1, comSubStr, allLcs);
return;
}
}
allLcs.add(comSubStr);
// System.out.println(comSubStr);
}
public static void main(String[] args) {
String str1 = "A1B2C3D";
String str2 = "A2BC";
System.out.println(getLongestCommonSubSequence(str1, str2));
}
}