Solving String reduction Algorithm

Question

Mi sto preparando per un'intervista che ho lunedì e ho trovato questo problema da risolvere chiamato "String Reduction". Il problema è espressa così:

Data una stringa contenente a, bec di, possiamo eseguire l'operazione seguente: Prendere due caratteri qualsiasi distinte adiacenti e sostituirlo con il terzo carattere. Ad esempio, se 'a' e 'c' sono adiacenti, possono essere sostituiti con 'b'. Qual è la stringa più piccola che può produrre applicando ripetutamente questa operazione?

Ad esempio, cab -> cc o cab -> bb, risultante in una stringa di lunghezza 2. Per questo, una soluzione ottimale è: bcab -> aab -> ac -> b. Nessun altro operazioni possono essere applicate e la stringa risultante ha lunghezza 1. Se la stringa è = CCCCC, non operazioni possono essere eseguite e quindi la risposta è 5.

Ho visto un sacco questions and answers su StackOverflow ma Vorrei verificare il mio algoritmo. Ecco il mio algoritmo in pseudo codice. Nel mio codice

1. S è la stringa di ridurre
2. S [i] è la caratteristica di indice i
3. P è una pila:

4. redux è la funzione che riduce i caratteri.

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

Il caso peggiore dei miei algoritmi è O (n), perché tutte le operazioni sulla pila P è in O (1). Ho provato questo algoritmo negli esempi sopra, ottengo le risposte attese. Permettetemi di eseguire il mio algo con questo esempio "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 

ho eseguito questo algoritmo su vari esempi come questo, sembra funzionare. Ho scritto un codice in Java che verifica questo algoritmo, quando invio il mio codice al sistema, ricevo risposte sbagliate. Ho pubblicato il codice java su gisthub in modo da poterlo vedere.

Qualcuno può dirmi cosa c'è di sbagliato nel mio algoritmo.

Answer 1

Ho intenzione di provare a spiegare che cosa significa nhahtdh. Esistono diversi motivi per cui l'algoritmo non riesce. Ma il più fondamentale è che in ogni momento, solo il primo personaggio osservato ha la possibilità di essere spinto nello stack p. Non dovrebbe essere così, dato che puoi iniziare una riduzione praticamente da qualsiasi posizione.

Consentitemi di darvi la stringa abcc.Se io punto di interruzione alla

car = S[i]; 

La corsa algo come:

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

A questo punto si è bloccato con una riduzione ccc

Ma c'è un'altra riduzione: abcc -> aac ->ab ->c

Inoltre, restituire la dimensione della pila P è errata. cc non può essere ridotto, ma l'algoritmo restituirà 1. Dovresti anche contare il numero di volte che salti.

Answer 2

si può anche risolvere questo problema usando la forza bruta ... e ricorsione

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 

La nuova stringa di lunghezza n-1 avrà n-2 coppie e similmente nuova stringa di lunghezza n-2 avrà n-3 coppie.

durante l'applicazione di questo approccio mantenere la memorizzazione del valore minimo

if (new_min < min) 
    min = new_min 

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