英文:
Why my logic for Longest Common Subsequence for 3 sequences is not robust?
问题
我对这个问题和我的解决方案有一个问题。给定三个序列 a、b、c - 我使用了找到每对(a, b)、(b, c)和(c, a))的最长公共子序列值的逻辑。然后找到这三个值中的最小值。这应该给我们最长的公共子序列值。
我想知道为什么我的解决方案不够健壮？我使用的代码如下（使用JAVA编写）。
驱动代码：
int result1 = DynamicProgramming.longestCommonSequence(a, b);
int result2 = DynamicProgramming.longestCommonSequence(b, c);
int result3 = DynamicProgramming.longestCommonSequence(c, a);
int temp = Math.min(result1, result2);
System.out.println(Math.min(result3, temp));
程序逻辑：
public static int longestCommonSequence(int[] a, int[] b) {
int[][] aS = new int[a.length + 1][b.length + 1];
int tempAS;
for (int i = 0; i < aS.length; i++)
for (int j = 0; j < aS[0].length; j++) {
if (i == 0) {
aS[i][j] = j;
} else if (j == 0) {
aS[i][j] = i;
} else {
int ins = aS[i][j - 1] + 1;
int del = aS[i - 1][j] + 1;
int mat = aS[i - 1][j - 1];
tempAS = Math.min(ins, del);
if (a[i - 1] == b[j - 1])
aS[i][j] = Math.min(mat, tempAS);
else
aS[i][j] = tempAS;
}
}
return (a.length + b.length - aS[a.length][b.length]) / 2;
}
这个程序在我尝试的所有测试案例中都有效。但是当我将它提交到一个在线自动测试器时，它在最后一个测试案例（edx课程）上失败了。我无法想象出解决方案失败的情况。任何帮助将不胜感激。
我们可以假设所有输入值都是有效的整数，数组a、b、c不为空。
PS：我已经找到了一个通过所有测试的替代解决方案。但我很好奇我的逻辑中的缺陷在哪里。谢谢。
英文:
I have a question regarding this problem and my solution. Given three sequences a,b,c - I used the logic of finding the longest common sub-sequence value of each pair (a,b), (b,c) and (c,a). Then finding the minimum of the three. Which should give us the longest common sub-sequence value.
I was wondering why my solution would not be robust? The code I used is below (in JAVA).
DRIVER CODE:
int result1 = DynamicProgramming.longestCommonSequence(a, b);
int result2 = DynamicProgramming.longestCommonSequence(b, c);
int result3 = DynamicProgramming.longestCommonSequence(c, a);
int temp = Math.min(result1, result2);
System.out.println(Math.min(result3, temp));
PROGRAM LOGIC:
public static int longestCommonSequence(int[] a, int[] b) {
int[][] aS = new int[a.length + 1][b.length + 1];
int tempAS;
for (int i = 0; i < aS.length; i++)
for (int j = 0; j < aS[0].length; j++) {
if (i == 0) {
aS[i][j] = j;
} else if (j == 0) {
aS[i][j] = i;
} else {
int ins = aS[i][j - 1] + 1;
int del = aS[i - 1][j] + 1;
int mat = aS[i - 1][j - 1];
tempAS = Math.min(ins, del);
if (a[i - 1] == b[j - 1])
aS[i][j] = Math.min(mat, tempAS);
else
aS[i][j] = tempAS;
}
}
return (a.length + b.length - aS[a.length][b.length]) / 2;
}
The program works in all test cases I have tried. But when I submitted it to an online automatic tester it failed on the last test case(edx course). I am unable to think of a situation where the solution would fail. Any help would be greatly appreciated.
We can assume that all input values are valid integers and the arrays a,b,c are not null.
PS: I have already found and alternate solution that passes all the tests. But I was curious to know the flaw in my logic. Thanks.
答案1
得分: 3
如果字符串a是aaaaaaabbbbbbb，字符串b是bbbbbbbbccccccc，字符串c是cccccccaa
aaaaaa，则(a,b)有一个长度为7的公共子序列，(b,c)有一个长度为7的公共子序列，
(c,a)有一个长度为7的公共子序列，但是是否存在一个在这三者中都是公共的子序列呢？
（答案：没有...因此仅仅取这三个成对比较的最小值的想法是有缺陷的）
英文:
if string a was aaaaaaaabbbbbbb
and string b was bbbbbbbbccccccc
and string c was ccccccccaaaaaaa
then (a,b) have a common subsequence of length 7
and (b,c) have a common subsequence of length 7
and (c,a) have a common subsequence of length 7
but is there a subsequence that is common to all 3?
(Answer: no... and so the idea of just taking the min of the 3 pairwise comparisons is flawed)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论