4

PS: これは、2 つのシーケンス間のオーバーラップを見つけて返す方法の複製ではありません。

[以下の問題に適用できる場合は、上記のアプローチで解決策を求めますが]

Q: うまくいきましたが、まだスケーラブルなソリューションではなく、明らかに最適化されていません (スコアが低い)。問題の次の説明を読んで、より良い解決策を提供してください。

質問：

簡単にするために、接頭辞と接尾辞は空ではなく、文字列 S 全体よりも短い必要があります。文字列の境界はS、接頭辞と接尾辞の両方である任意の文字列です。たとえば、"cut"は文字列の境界線であり、文字列"cutletcut"には と の"barbararhubarb"2 つの境界線が"b"あり"barb"ます。

class Solution { public int solution(String S); }

Sこれは、文字で構成される文字列を指定すると、指定された文字列Nで少なくとも 3 つの重複しないオカレンスを持つ最長の境界線の長さを返します。にそのような境界線がない場合S、関数は 0 を返す必要があります。

例えば、

  • 上記で説明したようにS = "barbararhubarb"、関数が を返す必要がある場合。1
  • S = "ababab"関数が を返す必要がある場合、と2は"ab"どちら"abab"も の境界ですが、重複しないオカレンスは 3 つSしかありません。"ab"
  • 唯一の境界線が 2 回しか発生しないS = "baaab"ため、関数が を返す必要がある場合。0"b"

と仮定する：

  • N範囲内の整数です[0..1,000,000]。
  • stringSは小文字 ( a−z) のみで構成されます。

複雑：

  • 予想される最悪の場合の時間計算量はO(N);
  • 予想される最悪の場合のスペースの複雑さはO(N)(入力引数に必要なストレージをカウントしない) です。

def solution(S):
    S = S.lower()
    presuf = []
    f = l = str()
    rank = []
    wordlen = len(S)
    for i, j in enumerate(S):
        y = -i-1
        f += S[i]
        l = S[y] + l
        if f==l and f != S:
            #print f,l
            new=S[i+1:-i-1]
            mindex = new.find(f)
            if mindex != -1:
                mid = f #new[mindex]
                #print mid
            else:
                mid = None
            presuf.append((f,mid,l,(i,y)))
    #print presuf
    for i,j,k,o in presuf:
        if o[0]<wordlen+o[-1]: #non overlapping
            if i==j:
                rank.append(len(i))
            else:
                rank.append(0)
    if len(rank)==0:
        return 0
    else:
        return max(rank)

私のソリューションの時間の複雑さは次のとおりです。 O(N 2) または O(N 4) 助けていただければ幸いです。

4

5 に答える 5

0

O(N) または O(N**3) を実行して全体で 90/100 を実現する (Java) ソリューションがありますが、2 つの異なるテストケースを実行する方法がわかりません。

ほぼすべて同じ文字 aaaaa...aa??aaaa??....aaaaaaa 2.150秒。タイムアウト エラー 実行時間: >2.15 秒、制限時間: 1.20 秒。

same_letters_on_both_ends 2.120 秒。TIMEOUT ERROR 実行時間: >2.12 秒、制限時間: 1.24 秒。

編集：それを釘付けにしました！ これで、O(N) で実行され、100/100 の結果のすべてのチェックに合格するソリューションができました :) Codility は知りませんでしたが、素晴らしいツールです!

于 2013-07-09T06:14:08.980 に答える
0 
protected int calcBorder(String input) {
    if (null != input) {
        int mean = (input.length() / 3);
        while (mean >= 1) {
            if (input.substring(0, mean).equals(
                    input.substring(input.length() - mean))) {
                String reference = input.substring(0, mean);
                String temp = input
                        .substring(mean, (input.length() - mean));
                int startIndex = 0;
                int endIndex = mean;
                int count = 2;
                while (endIndex <= temp.length()) {
                    if (reference.equals(temp.substring(startIndex,
                            endIndex))) {
                        count++;
                        if (count >= 3) {
                            return reference.length();
                        }
                    }
                    startIndex++;
                    endIndex++;
                }
            }
            mean--;
        }
    }
    return 0;
}
于 2014-12-16T15:51:45.223 に答える
0

Zアルゴリズムは良い解決策です。

于 2016-01-30T05:06:45.310 に答える