0

編集：アップ

以下の文字列ではコードが正しく動作しません。

"1 11 23 1 18 9 15 23 5"

"11 1 18 1 20 5 11 1"

編集: 2 番目の文字列で 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();

このコードの出力 (最初の 2 つの文字列) は次のとおりです。

11 1 18 1 2 5

ただし、出力は次のようになります。

11 1 18 5
4

1 に答える 1

1

完全な/より良い説明については、以下を参照してください。

配列を正しく構築していると思います。ただし、LCS を構築するためにテーブルが読み取られる方法についてはわかりません。

アイデアは、2D 配列 solution[str1.length()][str2.length()] の最後から開始することです。

  • str1 と str2 の最後の文字が等しい場合、最後の文字は LCS の一部であり、両方のインデックスをデクリメントします
  • 等しくない場合は、解[i-1][j]と解[i][j-1]を比較し、値が大きい方向に進みます。
  • いずれかのインデックスが 0 になるまで繰り返します。
于 2014-11-26T23:50:03.840 に答える