8

私は月曜日に行われる面接の準備をしていますが、「文字列削減」と呼ばれるこの問題を解決できることがわかりました。問題は次のように述べられています。

a、b、c で​​構成される文字列が与えられた場合、次の操作を実行できます。隣接する 2 つの異なる文字を取り、3 番目の文字に置き換えます。たとえば、「a」と「c」が隣接している場合、「b」に置き換えることができます。この操作を繰り返し適用して得られる最小の文字列は?

たとえば、cab -> cc または cab -> bb の場合、文字列の長さは 2 になります。この場合の最適なソリューションの 1 つは、bcab -> aab -> ac -> b です。これ以上操作を適用することはできず、結果の文字列の長さは 1 になります。文字列が CCCCC の場合、操作を実行できないため、答えは 5 です。

stackoverflow で多くの質問と回答を見てきましたが、独自のアルゴリズムを検証したいと思います。これが疑似コードでの私のアルゴリズムです。私のコードでは

  1. S は削減する文字列です
  2. S[i] はインデックス i の文字です
  3. P はスタックです。

  4. redux は文字を削減する関数です。

    function reduction(S[1..n]){        
P = create_empty_stack();
for i = 1 to n
do
   car = S[i];
   while (notEmpty(P))
   do
      head = peek(p);
      if( head == car) break;
      else {
         popped = pop(P);
         car = redux (car, popped);
       }  
   done
   push(car)
done
return size(P)}

私のアルゴリズムの最悪のケースは O(n) です。これは、スタック P のすべての操作が O(1) にあるためです。上記の例でこのアルゴリズムを試してみましたが、期待どおりの答えが得られました。この例「 abacbcaa」でアルゴを実行してみましょう。

i = 1 :
   car = S[i] = a, P = {∅}
   P is empty, P = P U {car} -> P = {a}

 i = 2 :
   car = S[i] = b, P = {a}
   P is not empty :
       head = a
       head != car ->
            popped = Pop(P) = a 
            car = reduction (car, popped) = reduction (a,b) = c
            P = {∅}

    push(car, P) -> P = {c}



i = 3 :
   car = S[i] = a, P = {c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (a,c) = b
            P = {∅}

    push(car, P) -> P = {b}


 ...


 i = 5 : (interesting case)
  car = S[i] = c, P = {c}
   P is not empty :
       head = c
       head == car -> break

    push(car, P) -> P = {c, c}


 i = 6 :
  car = S[i] = b, P = {c, c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (b,c) = a
            P = {c}

   P is not empty : // (note in this case car = a)
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (a,c) = b
            P = {∅}
    push(car, P) -> P = {b}

... and it continues until n

このようなさまざまな例でこのアルゴリズムを実行しましたが、うまくいくようです。このアルゴリズムをテストするコードを Java で作成しました。コードをシステムに送信すると、間違った回答が得られます。JavaコードをGisthubに投稿した ので、それを見ることができます。

誰かが私のアルゴリズムの何が問題なのか教えてもらえますか?

4

2 に答える 2

5

意味を説明しようと思いますnhahtdh。アルゴリズムが失敗する理由は複数あります。しかし、最も基本的なことは、各時点で最初に観測された文字のみがスタックにプッシュされる可能性があるということpです。基本的にどの位置からでも削減を開始できるため、この方法ではいけません。

文字列をあげましょう abcc。ブレークポイントを設定すると

car = S[i];

アルゴリズムは次のように実行されます。

p = {∅}, s = _abcc //underscore is the position
p = {a}, s = a_bcc  
p = {c}, s = ab_cc

この時点で、あなたは削減に行き詰まっていますccc

しかし、別の削減があります:abcc -> aac ->ab ->c

また、スタックのサイズを返すのPは間違っています。ccを減らすことはできませんが、アルゴリズムは を返し1ます。また、スキップした回数もカウントする必要があります。

于 2012-05-26T14:20:08.910 に答える
0

ブルートフォース...と再帰を使用してこの質問を解決することもできます

for all n-1 pairs(2 char) replace it with 3rd char if possible and apply reduce on this new string of length n-1
    for all n-2 pairs replace it with 3rd char and apply reduce on new string
         for all n-3 pairs....and so on

長さ n-1 の新しい文字列には n-2 ペアがあり、同様に長さ n-2 の新しい文字列には n-3 ペアがあります。

このアプローチを適用している間、最小値を保存し続けます

if (new_min < min)
    min = new_min

実装: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html

于 2012-06-13T09:33:15.880 に答える