Resolviendo Algoritmo de reducción de cadena

Question

Me estoy preparando para una entrevista que tengo el lunes y encontré este problema para resolver llamado "String Reduction". El problema se plantea así:

Dada una cadena que consta de A, B y C de, podemos realizar la siguiente operación : Tomar dos caracteres distintos adyacentes y reemplazarlo con el tercer personaje. Por ejemplo, si 'a' y 'c' son adyacentes, pueden reemplazarse por 'b'. ¿Cuál es la cadena más pequeña que puede resultar aplicando esta operación repetidamente?

Por ejemplo, cab -> cc o cab -> bb, lo que resulta en una cadena de longitud 2. Para esta, una solución óptima es: bcab -> aab -> ac -> b. No hay más operaciones pueden ser aplicadas y la cadena resultante tiene longitud 1. Si la cadena es = CCCCC, no hay operaciones se pueden realizar y por lo tanto la respuesta es 5.

he visto mucho questions and answers en StackOverflow pero Me gustaría verificar mi propio algoritmo. Aquí está mi algoritmo en pseudo código. En mi código

1. S es mi cadena para reducir
2. S [i] es el carácter en el índice i
3. P es una pila:

4. Redux es la función que reduce los personajes.

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

El peor caso de mis algoritmos es O (n), ya que todas las operaciones en la pila P está en O (1). Probé este algoritmo en los ejemplos anteriores, obtengo las respuestas esperadas. Déjame ejecuto mi algo con este ejemplo "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 

he ejecutar este algoritmo en varios ejemplos como este, parece que funciona. He escrito un código en Java que prueba este algoritmo. Cuando envío mi código al sistema, obtengo respuestas incorrectas. He publicado el código de Java en gisthub para que pueda verlo.

¿Puede alguien decirme qué está mal con mi algoritmo?

Answer 1

Voy a tratar de explicar qué significa nhahtdh. Hay varias razones por las cuales tu algoritmo falla. Pero la más fundamental es que en cada punto en el tiempo, solo el primer carácter observado tiene la oportunidad de ser empujado en la pila p. No debería ser así, ya que puedes comenzar una reducción básicamente desde cualquier posición.

Déjame darte la cadena abcc.Si punto de ruptura en

car = S[i]; 

La carrera algo como:

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

En este punto le pegan con una reducción ccc

Pero hay otra reducción: abcc -> aac ->ab ->c

Además, devolver el tamaño de la pila P es incorrecto. cc no se puede reducir, pero el algoritmo devolverá 1. También debe contar la cantidad de veces que omite.

Answer 2

también se puede resolver esta cuestión mediante la fuerza bruta ... y recursividad

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 nueva cadena de longitud n-1 tendrá n-2 pares y de manera similar nueva cadena de longitud n-2 tendrá n-3 pares.

al aplicar este enfoque mantener almacenar el valor mínimo

if (new_min < min) 
    min = new_min 

Implementación: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html