0

编辑：向上

该代码不能与下面的字符串一起正常工作。

"1 11 23 1 18 9 15 23 5"

"11 1 18 1 20 5 11 1"

编辑：我注意到，如果我在第二个字符串中将 20 更改为 40，则该函数可以正常工作......

对于字符串：

"12 4 55 11 8 43 22 90 5 88 15"

"15 66 4 36 43 22 78 88 32"

它工作正常。哪里有问题？

这是我的代码：

 int[][] tabelka = new int[linia1.length()+1][linia2.length()+1];


        for (int i = 0; i<linia1.length(); i++) {
            for (j = 0; j<linia2.length(); j++) {

                if ( linia1.charAt(i) == linia2.charAt(j) ) {
                    tabelka[i+1][j+1] = tabelka[i][j] + 1;
                }

                else {
                    tabelka[i+1][j+1] = Math.max(tabelka[i+1][j], tabelka[i][j+1]);
                }

            }
        }

        for (int i = 0; i<linia1.length(); i++) {
            for (j = 0; j<linia2.length(); j++) {
                System.out.println(tabelka[i][j]);
            }
        }

        StringBuffer podciag = new StringBuffer();

        for(int x = linia1.length(), y = linia2.length(); x != 0 && y != 0; ) {

            if( tabelka[x][y] == tabelka[x-1][y] ) {
                licznik++;
                x--;
            }

            else if( tabelka[x][y] == tabelka[x][y-1] ) {
                licznik++;
                y--;
            }

            else {
                licznik++;
                assert linia1.charAt(x-1) == linia2.charAt(y-1);
                podciag.append(linia1.charAt(x-1));
                x--;
                y--;
            }
        }

        String buff = podciag.reverse().toString();

此代码的输出（对于前两个字符串）是：

11 1 18 1 2 5

但是，输出应该是：

11 1 18 5
4

1 回答 1

1

有关完整/更好的解释，请参阅：

我认为您正在正确构建数组。但是，我不确定读取表格以构建 LCS 的方式。

这个想法是从二维数组解决方案[str1.length()][str2.length()] 的末尾开始，如果：

  • str1 和 str2 的最后一个字符相等，那么最后一个字符是 LCS 的一部分并减少两个索引
  • 如果它们不相等，则比较 solution[i-1][j] 和 solution[i][j-1] 并朝着更大值的方向前进。
  • 重复直到任一索引为 0。
于 2014-11-26T23:50:03.840 回答