为什么我的 3 个序列的最长公共子序列逻辑不可靠？

Question

我对这个问题和我的解决方案有疑问。给定三个序列 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：我已经找到并通过了所有测试的替代解决方案。但我很想知道我逻辑上的缺陷。谢谢

Answer 1

如果字符串 a 是 aaaaaaaabbbbbbb

字符串 b 是 bbbbbbbbccccccc

字符串 c 是 ccccccccaaaaaaa

那么(a,b)有一个长度为7的公共子序列和 (b,c) 有一个长度为 7 的公共子序列和 (c,a) 有一个长度为 7

的公共子序列

但是是否有一个子序列是所有 3 个共有的？（答案：不......所以只取 3 个成对比较中的最小值的想法是有缺陷的）

为什么我的 3 个序列的最长公共子序列逻辑不可靠？

Why my logic for Longest Common Subsequence for 3 sequences is not robust?

java

dynamic-programming

subsequence