2

文字列内の繰り返し文字列を削除するアルゴリズムを作成してみました。

例えば

入力: Hello 出力: Helo

入力: AAAAZZZZ5 出力: AZ5

入力: 「リンゴとリンゴとオレンジ」 出力: 「リンゴとオレンジ」

以下にアルゴリズムを書きました（JSFiddle here）

function removeRepeat(str)
{
    var index = 0;
    var tempS = str.length;
    var currentBuffer = "";
    var repeatCharIndex = 1;
    console.log(str);
    for (var i = 1; i < tempS; i++)
    {
        var curChar = str[i];
        for (var j = 0; j < i; j++)
        {
            // check if duplicate
            if (str[j] === curChar)
            {
                console.log("duplicate detected at index ",j,str[j],"and index",i,str[i])
                // we have duplicate! means we could potentially have a repeated set of characters
                // i, j have same character, so let's move both forward
                var aheadLeft=j, aheadRight=i;
                var diff = Math.min(aheadRight-aheadLeft,tempS-aheadRight);
                var repeat = true;
                for (var num = 1; num < diff; num++)
                {
                    // we go backwards...
                    // ashiash ...
                    // we are at __h___h, so now we go
                    // _s__s_
                    console.log("\tis ",str[aheadRight+num],str[aheadLeft+num])
                    if (str[aheadRight+num] !== str[aheadLeft+num])
                    {
                        repeat = false;
                        break;
                    }    
                }
                if (repeat){
                    console.log("found repeat!",str,str[aheadLeft],aheadLeft,str[aheadRight],aheadRight);
                    str = str.substring(0,aheadRight)+str.substring(aheadRight+diff)
                    return removeRepeat(str);
                }
                break;
            }
        }
    }
    return str;
}
console.log("New str: "+removeRepeat("nnnnnnnnzzzzzz1"));

私が抱えている問題は、アルゴリズムが正しい結果を生成しないことです"Apples and Apples and Oranges"

繰り返される文字列は次のようにApples andなり、結果は Apples and Oranges になるはずですが、取得しています

Aples and Apples and Orang

重複が全体像の一部であるかどうかを確認するためにアルゴリズムを修正する方法がわかりません。私が思いついたアイデアの 1 つは、ストリングを前方に進むのではなく、後方に進むことでした。どんなアイデア/ヒントも素晴らしいでしょう!

*編集: 元の例では十分に明確ではありませんでした。

入力は、繰り返しながら、より大きなものの一部であるためではなく、Hey Hi Hi Hi Hey Hi Hi Hi出力する必要がありますHey Hi Hi HiHey HiHi Hi HiHey Hi Hi Hi

Boots and Cats and Boots and Cats and YO等しいべきではBoots and Cats YoないBots and Cats and Boots and Cats and YO

4

2 に答える 2

0

私がお勧めするのは、最長の重複を削除する関数を作成し、必要に応じて複数回呼び出すことです。これは、仕様のあいまいさ (の多く) を取り除く最も簡単な方法だと思います。

それをしたい場合は、持っているコードを取得しますが、実際にコードを削除する代わりに、削除される量と場所を追跡するだけです。さらに削除する方法を見つけるたびに、その情報を更新してください。

次に、最後に、見つかった最大のチャンク (保持している情報) を削除します。

于 2013-06-21T18:15:43.357 に答える
0

これは、あなたが求めていることにかなり近いでしょう。あなたの例の 2 つはわずかな変更が必要だと思いますが、それらがなければ意味がないようです。

ジャバスクリプトでは、

str.replace(/(.+?)(\1)+/g, function(match, group){return group;})

ここで行っているのは、文字列 (グループ 1) の後にそれ自体が 1 回以上一致し、それを 1 つのインスタンスだけに置き換えることです。グループ 1 の一致は貪欲ではないため、の代わりにAAAA->が使用されます。AAA

テストケース:

1) "Apples and Apples and Oranges" -> "Apples and Oranges"
2) "Hey Hi Hi Hi Hey Hi Hi Hi" -> "Hey Hi Hey Hi"
3) "Hey Hi Hi Hi Hey Hi Hi Hi " -> "Hey Hi Hi Hi "
4) "Boots and Cats and Boots and Cats and YO" -> "Boots and Cats and YO"
5) "AAAAZZZZ5" -> "AZ5"

2) は質問と一致しないことに注意してください。ただし、探している繰り返しが実際にそこにあるためには、そのスペースが必要です。3) は、ご想像のとおり、このケースを解決することを示していると思います。

また、4) は完全には一致しませんが、質問のタイプミスだと思います。

于 2013-06-21T21:23:20.000 に答える