私は月曜日に行われる面接の準備をしていますが、「文字列削減」と呼ばれるこの問題を解決できることがわかりました。問題は次のように述べられています。
a、b、c で構成される文字列が与えられた場合、次の操作を実行できます。隣接する 2 つの異なる文字を取り、3 番目の文字に置き換えます。たとえば、「a」と「c」が隣接している場合、「b」に置き換えることができます。この操作を繰り返し適用して得られる最小の文字列は?
たとえば、cab -> cc または cab -> bb の場合、文字列の長さは 2 になります。この場合の最適なソリューションの 1 つは、bcab -> aab -> ac -> b です。これ以上操作を適用することはできず、結果の文字列の長さは 1 になります。文字列が CCCCC の場合、操作を実行できないため、答えは 5 です。
stackoverflow で多くの質問と回答を見てきましたが、独自のアルゴリズムを検証したいと思います。これが疑似コードでの私のアルゴリズムです。私のコードでは
- S は削減する文字列です
- S[i] はインデックス i の文字です
- P はスタックです。
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に投稿した ので、それを見ることができます。
誰かが私のアルゴリズムの何が問題なのか教えてもらえますか?