Resolver el desafío de "reducción de cadena"

Question

He visto varias discusiones e intentos de código para resolver el problema "String reduction" de interviewstreet.com, pero ninguno de ellos lo hace mediante programación dinámica.

enumerados en la sección Dynamic Programming, el problema se describe como sigue:

Dada una cadena que consta de A, B y C de, podemos realizar la siguiente operación: tomar cualquier dos personajes distintas 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 al aplicar esta operación varias veces?

El problema se puede resolver utilizando exhaustiva búsqueda de fuerza bruta, creando un árbol de todas las sustituciones posibles:

// this is more or less pseudo code from my head 
int GetMinLength(string s) 
{ 
    // solve edge cases 
    if (s.Length == 1) return 1; 
    if (s.Length == 2) return ReduceIfPossible(s); 

    // recursive brute force 
    int min = s.Length; 
    for (int i = 0; i<s.Length-1; i++) 
    { 
     if (s[i] != s[i+1]) 
     { 
      var next = GetMinLength(
        s.Substring(0, i) + 
        Reduce(s[i], s[i + 1]) + 
        s.Substring(i + 2) 
       ); 

      if (next < min) min = next; 
     } 
    } 
} 

Esta falla, obviamente, para ampliar la N (N <= 100), por lo que estoy tratando de romper en subproblemas más pequeños, memorizarlos y fusionar resultados.

El problema es que no puedo determinar el estado que tendría "optimal substructure", necesario para aplicar la programación dinámica (o en otras palabras, para "fusionar" los resultados de los sub-problemas). Minimizar una parte de la cadena no garantiza que la cadena final sea realmente la solución más pequeña.

¿Cuál sería el subproblema "estado" en este caso, que podría fusionarse hacia la solución final?

Answer 1

Lo que hace que esto sea complicado es que debe tratar esto como 2 problemas dinámicos de programación seguidos.

1. Crea una tabla de, por carácter que termines, por posición inicial, todas las posibles posiciones finales que son un bloque que se puede reducir a ese personaje.
2. La longitud más pequeña a la que se pueden reducir los caracteres i finales de la cadena. (La tabla que construyó en el paso 1 puede usarse para reducir recursivamente este problema a subproblemas ya resueltos.)

El segundo proporciona su respuesta. Es mucho más sencillo si ya ha resuelto el primero.

Answer 2

Comienza por crear una estructura que describa una teoría de soluciones. Incluye la cantidad de caracteres considerados, y la cadena codificada hasta el momento, y el peor caso y el mejor caso para la teoría.

Al principio solo hay una teoría: no se procesan los caracteres. El mejor caso es una cadena de longitud 1 (por ejemplo, una regla siempre se aplica y la cadena se puede reducir a un carácter, y el peor caso es N, donde no se aplican las reglas) P. ej.

encoded string = ""; 
encoded index = 0; 
worst case = N; 
best case = 1; 

Ahora comience a incrementar el índice en uno, y agregue un carácter a la cadena codificada. Si no se aplican reglas, mantén intacta esa teoría. Si se aplica una regla, debe tomar una decisión, ya sea aplicar la regla o no. Entonces, cuando agrega un personaje, duplica la teoría para cada regla que podría aplicarse al último personaje y conserva una versión para ninguna regla aplicada. Y actualizas el mejor caso y el peor caso para cada teoría.

Al principio, el número de teorías se multiplicará muy rápidamente. Pero finalmente llegas a una situación en la que el peor de los casos es mejor que el mejor de los casos para otras teorías.

De modo que cada vez que avanza en el índice, elimina las teorías donde el mejor de los casos es peor que la teoría con el mejor peor de los casos. A medida que el índice se acerca a N, la mayoría de las teorías desaparecerán. código

Answer 3

Spoiler de alerta:

public static int findMinReduction(String line){ 
    //Pseudocode: 
    //Count the number of occurences of each letter in the input string. 
    //If two of these counts are 0, then return string.length 
    //Else if (all counts are even) or (all counts are odd), then return 2 
    //Else, then return 1 

    int len = line.length(); 
    String a_reduce = line.replaceAll("c", "").replaceAll("b", ""); 
    String b_reduce = line.replaceAll("a", "").replaceAll("c", ""); 
    String c_reduce = line.replaceAll("a", "").replaceAll("b", ""); 

    int a_occurances = a_reduce.length(); 
    int b_occurances = b_reduce.length(); 
    int c_occurances = c_reduce.length(); 

    if ((a_occurances == b_occurances && a_occurances == 0) || 
     (a_occurances == c_occurances && a_occurances == 0) || 
     (b_occurances == c_occurances && b_occurances == 0)){ 
     return len; 
    } 
    else{ 
     if (a_occurances % 2 == 0 && 
      b_occurances % 2 == 0 && 
      c_occurances % 2 == 0){ 
      return 2; 
     } 
     if (a_occurances % 2 != 0 
      && b_occurances % 2 != 0 && 
      c_occurances % 2 != 0){ 
      return 2; 
     } 
    } 
    return 1; 
} 

Complejidad:

Este es un O (n) la operación del tiempo la complejidad, como que aumenta el tamaño de entrada, la cantidad de trabajo a realizar es lineal con el tamaño de la entrada. Lo cual es increíblemente rápido, podemos procesar cadenas de tamaño megabyte y aún procesarlas en fracciones de segundo.

Algoritmo encontrar aquí con un completo análisis de por qué funciona este algoritmo:

stumped on a Java interview, need some hints