文字列削減アルゴリズムを解決する

Question

私は月曜日に行ったインタビューのために自分自身を準備しています。この問題を解決して "String Reduction"という名前の問題が見つかりました。問題はこのように述べている：

は、a、b及びcのからなる文字列を考えると、我々は次のよう 操作を行うことができます任意の2つの隣接の異なる文字を取り、3番目の文字で を交換してください。たとえば、 'a'と 'c'が隣接している場合、 は 'b'で置き換えることができます。この操作を繰り返して適用すると、 の結果が得られる最小の文字列は何ですか？

たとえば、cab - > ccまたはcab - > bbで、長さが の文字列になります。2.これは、bcab - > aab - > ac - > bです。これ以上の操作は適用されず、結果の文字列は、文字列は= CCCCCであれば、何も操作を行うことができないので、 答えは5

私はstackoverflowの上でたくさん questions and answersを見てきました

が、ある長さ1 を持ってすることができます自分のアルゴリズムを検証したいと思います。私のアルゴリズムは擬似コードです。私のコード

1. でSは、私の文字列がインデックスで
2. S [i]にある文字を削減することである私
3. Pがスタックです：

4. Reduxのは、文字を低減する機能です。スタックP上のすべての操作はO（1）であるため

   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）です。私は上記の例でこのアルゴリズムを試して、私は期待される答えを得る。私はこのような様々な例で、このアルゴリズムを実行している

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 

、動作しているようです： 私はこの例で「abacbcaaを」私のアルゴを実行してみましょう。 私はこのアルゴリズムをテストするJavaでコードを書いています。コードをシステムに提出すると、私は間違った答えを得ています。私はgisthubにJavaコードを掲載していますので、あなたはそれを見ることができます。

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

Answer 1

私は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を返します。スキップした回数もカウントする必要があります。

Answer 2

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

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があります-2のnペアと同様に新しい長さの文字列のn-2を持っていますn-3対。このアプローチを適用しながら

保つ最小値を格納

if (new_min < min) 
    min = new_min 

実装：文字列を軽減する方法が複数ある場合、それは、最小の文字列を求めているhttp://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html