问题描述
[注意:我事先搜索过,找不到解决所有子序列LCS问题的建议.]
[NOTE: I searched beforehand and couldn't find advice on solving the LCS problem for all subsequences.]
我在编写最长公共子序列"问题的解决方案时遇到了麻烦,在该问题中,我返回了两个输入字符串的所有最长公共子序列.我查看了维基百科页面,并尝试在其中实施伪代码,但遇到了我的"backtrackAll"方法出现问题.我相信我在下面正确地计算了LCS矩阵,但是我的"backtrackAll"方法返回了一个空集.关于我在做什么的任何提示吗?
I'm having trouble coding up a solution to the "longest common subsequence" problem where I return all the longest common subsequences for two input Strings. I looked at the Wikipedia page and tried to implement the pseudo-code on there, but ran into a problem with my "backtrackAll" method. I believe I'm computing the LCS matrix correctly below, but my "backtrackAll" method returns an empty set. Any tips on what I'm doing wrong?
public static void main (String[] args) {
String s1 = "AGCAT";
String s2 = "GAC";
int[][] matrix = computeMatrix(s1,s2);
HashSet<String> set = backtrackAll(matrix,s1,s2,s1.length(),s2.length());
//more stuff would go here...
}
private static int[][] computeMatrix(String s1, String s2) {
int[][] C = new int[s1.length()+1][s2.length()+1];
for (int i = 1; i < s1.length()+1; i++) {
for (int j = 1; j < s2.length()+1; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
C[i][j] = C[i-1][j-1] + 1;
} else {
C[i][j] = Math.max(C[i][j-1], C[i-1][j]);
}
}
}
return C;
}
private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
if (i == 0 || j == 0) {
return new HashSet<String>();
} else if (s1.charAt(i-1) == s2.charAt(j-1)) {
HashSet<String> R = backtrackAll(C,s1,s2,i-1,j-1);
HashSet<String> new_set = new HashSet<String>();
for (String Z: R) {
new_set.add(Z + s1.charAt(i-1));
}
return new_set;
} else {
HashSet<String> R = new HashSet<String>();
if (C[i][j-1] >= C[i-1][j]) {
R = backtrackAll(C, s1, s2, i, j-1);
}
if (C[i-1][j] >= C[i][j-1]) {
R.addAll(backtrackAll(C,s1,s2,i-1,j));
}
return R;
}
}
推荐答案
我对其进行了一些修改.现在可以使用了.您还应该考虑何时返回null HashSet
,在这种情况下,必须添加最后一个匹配的字符.
I modified it a bit. It now works. You should also consider when a null HashSet
is returned in whose case the last matched character has to be added.
private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
// System.out.println(i+" " + j);
if (i == 0 || j == 0) {
// System.out.println("0t");
return new HashSet<String>();
} else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// System.out.println("2t");
HashSet<String> R = backtrackAll(C, s1, s2, i - 1, j - 1);
HashSet<String> new_set = new HashSet<String>();
for (String Z : R) {
// System.out.println("1t");
new_set.add(Z + s1.charAt(i - 1));
}
new_set.add("" + s1.charAt(i - 1));
return new_set;
} else {
// System.out.println("3t");
HashSet<String> R = new HashSet<String>();
if (C[i][j - 1] >= C[i - 1][j]) {
R = backtrackAll(C, s1, s2, i, j - 1);
}
if (C[i - 1][j] >= C[i][j - 1]) {
R.addAll(backtrackAll(C, s1, s2, i - 1, j));
}
return R;
}
}
这篇关于所有最长的公共子序列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!