数据结构与算法:最长公共子序列(二)_请叫我大虾的博客-爱代码爱编程
描述
给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列
public class LcsSolve {
private String x;
private String y;
//private String res = "";
public String ans(int r,int c, int[][] b){
String res = "";
if(r == 0 || c == 0){
return res;
}
if(b[r][c] == 1){
res += ans(r-1,c-1,b);
res += x.charAt(r-1);
//System.out.println(res);
}else if(b[r][c] == 2){
res += ans(r-1,c,b);
}else if(b[r][c] == 3){
res+=ans(r,c-1,b);
}
return res;
}
public String LCS(String s1, String s2){
x = s1;
y = s2;
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1+1][len2+1];
int[][] b = new int[len1+1][len2+1]; // 记录位置
for (int i = 1; i < len1+1; i++) {
for (int j = 1; j < len2+1; j++) {
if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
b[i][j] = 1; // 从左上方到当前位置
}else{
if(dp[i-1][j] > dp[i][j-1]){
dp[i][j] = dp[i-1][j];
b[i][j] = 2; // 从上方到当前位置
}else{
dp[i][j] = dp[i][j-1];
b[i][j] = 3; // 从左方到当前位置
}
}
}
}
//System.out.println(dp[len1][len2]);
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[0].length; j++) {
System.out.print(b[i][j]+" ");
}
System.out.println();
}
String res = ans(len1,len2,b);
//System.out.println(res);
if(res.isEmpty()){
return "-1";
}else{
return res;
}
}
public static void main(String[] args) {
LcsSolve lcsSolve = new LcsSolve();
String s1 = "A12C3D4B56";
String s2 = "B1D23A456A";
s2 = "90";
System.out.println(lcsSolve.LCS(s1,s2));
}
}