Convierte cadena en cadena palindrómica con inserciones mínimas

Question

Para encontrar el número mínimo de inserciones necesarias para convertir una cadena dada en palindrome, encuentro la subsecuencia común más larga de la cadena (lcs_string) y su inversa. Por lo tanto, el número de inserciones que se realizarán es length (s) - length (lcs_string)

¿Qué método se debe emplear para encontrar el string palindrome equivalente al conocer el número de inserciones que se realizarán?

Por ejemplo:

1) azbzczdzez

número de inserciones requeridas: 5 cadena palíndromo: azbzcezdzeczbza

Aunque varias cadenas palíndromo pueden existir para la misma cadena pero quiero encontrar una sola ¿palíndromo?

Answer 1

Deje S[i, j] representa una sub-secuencia de la cadena S a partir de índice de i y terminando en el índice j (ambos inclusive) y c[i, j] ser la solución óptima para S[i, j].

Obviamente, c[i, j] = 0 if i >= j.

En general, tenemos la recurrencia:

Answer 2

La solución parece ser una solución de programación dinámica.

Usted puede ser capaz de encontrar su respuesta en el siguiente mensaje: How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

dar más detalles sobre VenomFangs respuesta, no es una solución de programación dinámica simple de éste. Tenga en cuenta que supongo que la única operación permitida aquí es la inserción de caracteres (sin eliminación, actualizaciones). Deje que S sea una cadena de n caracteres. El simple función de recursividad P para esto es:

= P [i+1 .. j-1], if S[i] = S[j] 

P [i..j]

= min (P[i..j-1], P[i+1..j]) + 1, 

Si desea una explicación más detallada acerca de por qué esto es cierto, colocar un comentario y me ser feliz de explicar (aunque es bastante fácil de ver con un poco de pensamiento). Esto, dicho sea de paso, es exactamente lo contrario de la función LCS que utiliza, por lo tanto, valida que su solución es, de hecho, óptima. Por supuesto que es totalmente posible que me haya equivocado, si es así, ¡alguien hágamelo saber!

Editar: Para tener en cuenta la propia palíndromo, esto se puede hacer fácilmente de la siguiente manera: Como se indicó anteriormente, P [1..n] le daría el número de inserciones necesarias para que esta cadena un palíndromo. Una vez que se construye el conjunto de dos dimensiones anterior, así es como se encuentra el palíndromo:

Comience con i = 1, j = n. Ahora, string output = "";

while(i < j) 
{ 
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point 
    { 
     output = output + S[i]; 
     i++; 
     j--; 
    } 
    else 
    if (P[i][j] == P[i+1][j]) // 
    { 
     output = output + S[i]; 
     i++; 
    } 
    else 
    { 
     output = S[j] + output; 
     j--; 
    } 
} 
cout<<output<<reverse(output); 
//You may have to be careful about odd sized palindromes here, 
// I haven't accounted for that, it just needs one simple check 

¿Lees una mejor lectura?

Answer 4

simple.Véase más adelante :)

 String pattern = "abcdefghgf"; 
     boolean isPalindrome = false; 
     int i=0,j=pattern.length()-1; 
     int mismatchCounter = 0; 

     while(i<=j) 
     { 
      //reverse matching 
      if(pattern.charAt(i)== pattern.charAt(j)) 
       { 
        i++; j--; 
        isPalindrome = true; 
        continue; 
       } 

      else if(pattern.charAt(i)!= pattern.charAt(j)) 
       { 
        i++; 
        mismatchCounter++; 
       } 


     } 
     System.out.println("The pattern string is :"+pattern); 
     System.out.println("Minimum number of characters required to make this string a palidnrome : "+mismatchCounter); 

Answer 5

PHP solución de O (n)

function insertNode(&$arr, $idx, $val) { 
    $arr = array_merge(array_slice($arr, 0, $idx), array($val), array_slice($arr, $idx)); 
} 
function createPalindrome($arr, $s, $e) { 
    $i = 0; 
    while(true) { 
     if($s >= $e) { 
      break; 
     } else if($arr[$s] == $arr[$e]) { 
      $s++; $e--; // shrink the queue from both sides 
      continue; 
     } else { 
      insertNode($arr, $s, $arr[$e]); 
      $s++; 
     } 
    } 
    echo implode("", $arr); 
} 
$arr = array('b', 'e', 'a', 'a', 'c', 'd', 'a', 'r', 'e'); 
echo createPalindrome ($arr, 0, count ($arr) - 1);