5

だから私は、カリブのオンライン裁判官のウェブページhttp://coj.uci.cu/24h/problem.xhtml?abb=1772の問題 1772 を解決しようとしています。その中に少なくとも 1 つの回文:

たとえば、次の文字列から取得した部分文字列を分析します: "baraabarbabartaarabcde"

「バラ」には回文「アラ」が含まれます

「abar」には回文「aba」が含まれます

「babar」には回文「babar」が含まれています

「taar」には回文「aa」が含まれます

"abcde" には回文が含まれていません。

などなどなど...

最初の文字と最後の文字から同時に文字列を繰り返し、次のパターンのみを探して文字列の中心に向かって進んでいるため、私のアプローチは本当に速いと思います: "aa" "aba"与えられた部分文字列には回文が含まれていると言えます。問題は、アルゴリズムに時間がかかっていることですが、問題を見つけることができません。私がこれで本当に迷っていることを見つけるのを手伝ってください。これが私のアルゴリズムです

public static boolean hasPalindromeInside(String str)
{
    int midpoint=(int) Math.ceil((float)str.length()/2.0);
    int k = str.length()-1;

    for(int i = 0; i < midpoint;i++)
    {
        char letterLeft = str.charAt(i);
        char secondLetterLeft=str.charAt(i+1);
        char letterRight = str.charAt(k);
        char secondLetterRight =  str.charAt(k-1);

        if((i+2)<str.length())
        {
            char thirdLetterLeft=str.charAt(i+2);
            char thirdLetterRight=str.charAt(k-2);


            if(letterLeft == thirdLetterLeft || letterRight == thirdLetterRight)
            {
                return true;
            }

        }


        if(letterLeft == secondLetterLeft || letterRight==secondLetterRight)
        {
            return true;
        }

    k--;
    }
    return false;
}
}

入力文字列と部分文字列の間隔を取得するコードを削除しました。部分文字列を取得するために String.substring() を使用していますが、それが問題の原因になるとは思いません。そのコードが必要な場合はお知らせください。ありがとう！

4

1 に答える 1

1

2 文字と 3 文字の回文すべての位置を見つけるために O(n) 前処理を行うと、クエリごとに O(1) 時間でこれを解決できると思います。(偶数のプレーンドロームには中央に 2 文字のプレーンドロームがあり、奇数のプレーンドロームには 3 文字のプレーンドロームがあるため、2 と 3 をチェックするだけで十分です。)

例えば、

文字列 baraabarbabartaarabcde を指定して、最初に 2 文字の回文の位置を示す配列を計算します。

baraabarbabartaarabcde
000100000000001000000-

次に、この配列の累積合計を計算します。

baraabarbabartaarabcde
000100000000001000000-
000111111111112222222-

減算を行うと、クエリ範囲に 2 文字の回文があるかどうかをすぐに判断できます。

同様に、3 文字のプレーンドロームの場合:

baraabarbabartaarabcde  String
01001000100000010000--  Indicator
01112222333333344444--  Cumulative
于 2013-10-06T20:08:09.127 に答える