[注意:我事先进行了搜索,但找不到有关解决所有子序列的 LCS 问题的建议。]
我在编写“最长公共(public)子序列”问题的解决方案时遇到问题,我返回两个输入字符串的所有最长公共(public)子序列。我看着 Wikipedia page并尝试在那里实现伪代码,但遇到了我的“backtrackAll”方法的问题。我相信我在下面正确计算了 LCS 矩阵,但我的“backtrackAll”方法返回一个空集。关于我做错了什么的任何提示?
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;
}
}
最佳答案
我稍微修改了一下。现在可以了。您还应该考虑何时返回空 HashSet
,在这种情况下必须添加最后一个匹配的字符。
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;
}
}
关于java - 所有最长公共(public)子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7369025/