Rozwiązywanie algorytmu redukcji ciągu

Question

Przygotowuję się do wywiadu, który mam w poniedziałek i znalazłem ten problem do rozwiązania o nazwie "String Reduction". Problemem jest powiedziane tak:

Biorąc pod uwagę ciąg składający się z ciągu, B i C, możemy wykonać następującą operację : Weźmy dowolne dwa sąsiadujące ze sobą różne postacie i zastąpić go z trzecim znaku. Na przykład, jeśli "a" i "c" sąsiadują ze sobą, mogą one zostać zastąpione przez "b". Jaki jest najmniejszy ciąg znaków, który można uzyskać, powtarzając tę ​​operację?

Na przykład kabina -> cc lub kabina -> bb, co daje ciąg o długości 2. W tym przypadku jednym optymalnym rozwiązaniem jest: bcab -> aab -> ac -> b. Brak więcej operacji mogą być stosowane i otrzymany łańcuch ma długość 1. Jeśli łańcuch jest = CCCCC żadne operacje mogą być wykonywane, a więc odpowiedź brzmi 5.

Widziałem wiele questions and answers na stackoverflow, ale Chciałbym zweryfikować mój własny algorytm. Oto mój algorytm w pseudo kodzie. W moim kodu

1. S jest mój ciąg zmniejszyć
2. s [i] to postać w indeksie i
3. P jest stosem:

4. Redux to funkcja, która zmniejsza znaki.

   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)} 
   

Najgorszym z moich algorytmów O (N), ponieważ wszystkie operacje na stosie P jest O (1). Próbowałem tego algorytmu w powyższych przykładach, otrzymałem oczekiwane odpowiedzi. Pozwól mi wykonać moją algo z tym przykładzie „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 

mam uruchomić ten algorytm na różnych przykładów takich jak ten, wydaje się działać. Napisałem kod w języku Java, który testuje ten algorytm, kiedy przesyłam mój kod do systemu, otrzymuję błędne odpowiedzi. Wysłałem kod Java na gisthub, abyś mógł go zobaczyć.

Czy ktoś może mi powiedzieć, co jest nie tak z moim algorytmem.

Answer 1

Mam zamiar spróbować wyjaśnić, co oznacza nhahtdh. Istnieje wiele przyczyn niepowodzenia Twojego algorytmu. Ale najbardziej podstawowym jest to, że w każdym momencie tylko pierwsza obserwowana postać ma szansę zostać zepchnięta na stos p. Nie powinno tak być, ponieważ możesz zacząć redukcję zasadniczo z dowolnej pozycji.

Pozwól, że dam ci ciąg abcc.Gdybym przerwania na

car = S[i]; 

Bieg algo jak:

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

W tym momencie utkniesz ze zmniejszeniem ccc

Ale jest też inna redukcja: abcc -> aac ->ab ->c

Poza tym, zwracanie rozmiaru stosu P jest nieprawidłowe. cc nie można zmniejszyć, ale algorytm zwróci Powinieneś także policzyć liczbę pomijania.

Answer 2

można również rozwiązać tę kwestię za pomocą brutalnej siły ... i rekurencji

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 

Nowy ciąg długości n-1 będzie miał N2-pair i podobnie nowy łańcuch o długości N-2 będą miały pary n-3.

przy zastosowaniu tego podejścia zachować przechowywania wartości minimalnej

if (new_min < min) 
    min = new_min 

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