programa en C++ para encontrar inserciones mínimas para formar un palíndromo | DP-28

Dada la string str , la tarea es encontrar la cantidad mínima de caracteres que se insertarán para convertirla en un palíndromo.

Antes de continuar, entendamos con algunos ejemplos: 

• ab: el número de inserciones necesarias es 1, es decir, b ab
• aa: el número de inserciones requeridas es 0, es decir, aa
• abcd: el número de inserciones necesarias es 3, es decir , dcb abcd
• abcda: El número de inserciones requeridas es 2, es decir, un dc bcda que es el mismo que el número de inserciones en la substring bcd (¿Por qué?).
• abcde: el número de inserciones necesarias es 4, es decir , edcb abcde

Deje que la string de entrada sea str[l……h] . El problema se puede dividir en tres partes:  

1. Encuentre el número mínimo de inserciones en la substring str[l+1,…….h].
2. Encuentre el número mínimo de inserciones en la substring str[l…….h-1].
3. Encuentre el número mínimo de inserciones en la substring str[l+1……h-1].

Enfoque recursivo : el número mínimo de inserciones en la string str[l…..h] se puede dar como:  

• minInsertions(str[l+1…..h-1]) si str[l] es igual a str[h]
• min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 en caso contrario

A continuación se muestra la implementación del enfoque anterior:  

// A Naive recursive program to find minimum 
// number insertions needed to make a string
// palindrome
#include<bits/stdc++.h>
using namespace std;
  
  
// Recursive function to find  
// minimum number of insertions
int findMinInsertions(char str[], 
                      int l, int h)
{
    // Base Cases
    if (l > h) 
        return INT_MAX;
  
    if (l == h) 
        return 0;
  
    if (l == h - 1) 
        return (str[l] == str[h]) ? 0 : 1;
  
    // Check if the first and last characters are
    // same. On the basis of the comparison result, 
    // decide which subrpoblem(s) to call
    return (str[l] == str[h])? 
            findMinInsertions(str, l + 1, h - 1):
            (min(findMinInsertions(str, l, h - 1),
             findMinInsertions(str, l + 1, h)) + 1);
}
  
// Driver code
int main()
{
    char str[] = "geeks";
    cout << findMinInsertions(str, 0, 
                              strlen(str) - 1);
    return 0;
}
// This code is contributed by Akanksha Rai

Producción: 

3

Solución basada en programación dinámica 
Si observamos cuidadosamente el enfoque anterior, podemos encontrar que presenta subproblemas superpuestos . 
Supongamos que queremos encontrar el número mínimo de inserciones en la string «abcde»:  

                      abcde
            /       |      
           /        |        
           bcde         abcd       bcd  <- case 3 is discarded as str[l] != str[h]
       /   |          /   |   
      /    |         /    |    
     cde   bcd  cd   bcd abc bc
   / |   / |  /| / | 
de cd d cd bc c………………….

Las substrings en negrita muestran que la recursividad debe terminar y el árbol de recurrencia no puede originarse desde allí. La substring del mismo color indica subproblemas superpuestos .

¿Cómo reutilizar soluciones de subproblemas? La técnica de memorización se utiliza para evitar recordar subproblemas similares. Podemos crear una tabla para almacenar los resultados de los subproblemas para que puedan usarse directamente si se vuelve a encontrar el mismo subproblema.
La siguiente tabla representa los valores almacenados para la string abcde. 

a b c d e
----------
0 1 2 3 4
0 0 1 2 3 
0 0 0 1 2 
0 0 0 0 1 
0 0 0 0 0

¿Cómo llenar la mesa?  
La tabla debe llenarse en forma diagonal. Para la string abcde, 0….4, se debe ordenar lo siguiente en que se llena la tabla:

Gap = 1: (0, 1) (1, 2) (2, 3) (3, 4)
Gap = 2: (0, 2) (1, 3) (2, 4)

Gap = 3: (0, 3) (1, 4)

Gap = 4: (0, 4)

A continuación se muestra la implementación del enfoque anterior: 

// A Dynamic Programming based program to find 
// minimum number insertions needed to make a 
// string palindrome 
#include <bits/stdc++.h>
using namespace std;
  
  
// A DP function to find minimum
// number of insertions 
int findMinInsertionsDP(char str[], int n) 
{ 
    // Create a table of size n*n. table[i][j] 
    // will store minimum number of insertions 
    // needed to convert str[i..j] to a palindrome. 
    int table[n][n], l, h, gap; 
  
    // Initialize all table entries as 0 
    memset(table, 0, sizeof(table)); 
  
    // Fill the table 
    for (gap = 1; gap < n; ++gap) 
        for (l = 0, h = gap; h < n; ++l, ++h) 
            table[l][h] = (str[l] == str[h])? 
                           table[l + 1][h - 1] : 
                           (min(table[l][h - 1], 
                            table[l + 1][h]) + 1); 
  
    // Return minimum number of insertions
    // for str[0..n-1] 
    return table[0][n - 1]; 
} 
  
// Driver Code
int main() 
{ 
    char str[] = "geeks"; 
    cout << findMinInsertionsDP(str, 
                                strlen(str)); 
    return 0; 
} 
// This is code is contributed by rathbhupendra

Producción: 

3

Complejidad temporal: O(N^2) 
Espacio auxiliar: O(N^2)

Otra solución de programación dinámica (variación del problema de la subsecuencia común más larga) 
El problema de encontrar inserciones mínimas también se puede resolver utilizando el problema de la subsecuencia común más larga (LCS) . Si averiguamos el LCS de string y su reverso, sabemos cuántos caracteres como máximo pueden formar un palíndromo. Necesitamos insertar los caracteres restantes. Los siguientes son los pasos. 

1. Encuentre la longitud de LCS de la string de entrada y su reverso. Sea la longitud ‘l’.
2. El número mínimo de inserciones necesarias es la longitud de la string de entrada menos ‘l’.

A continuación se muestra la implementación del enfoque anterior:  

// An LCS based program to find minimum number 
// insertions needed to make a string palindrome 
#include <bits/stdc++.h>
using namespace std;
   
// Returns length of LCS for X[0..m-1], 
// Y[0..n-1]. 
int lcs(string X, string Y, 
        int m, int n) 
{ 
    int L[m+1][n+1]; 
    int i, j; 
      
    /* Following steps build L[m+1][n+1] in 
       bottom up fashion. Note that L[i][j]  
       contains length of LCS of X[0..i-1] 
       and Y[0..j-1] */
    for (i = 0; i <= m; i++) 
    { 
        for (j = 0; j <= n; j++) 
        { 
        if (i == 0 || j == 0) 
            L[i][j] = 0; 
      
        else if (X[i - 1] == Y[j - 1]) 
            L[i][j] = L[i - 1][j - 1] + 1; 
      
        else
            L[i][j] = max(L[i - 1][j], 
                          L[i][j - 1]); 
        } 
    } 
      
    /* L[m][n] contains length of LCS for 
       X[0..n-1] and Y[0..m-1] */
    return L[m][n]; 
} 
  
void reverseStr(string& str) 
{ 
    int n = str.length(); 
  
    // Swap character starting from two 
    // corners 
    for (int i = 0; i < n / 2; i++) 
        swap(str[i], str[n - i - 1]); 
} 
  
// LCS based function to find minimum 
// number of insertions 
int findMinInsertionsLCS(string str, int n) 
{ 
    // Creata another string to store 
    // reverse of 'str' 
    string rev = ""; 
    rev = str; 
    reverseStr(rev); 
      
    // The output is length of string minus 
    // length of lcs of str and it reverse 
    return (n - lcs(str, rev, n, n)); 
} 
  
// Driver code
int main() 
{ 
    string str = "geeks"; 
    cout << findMinInsertionsLCS(str, 
                                 str.length()); 
    return 0; 
} 
// This code is contributed by rathbhupendra

Producción: 

3

Complejidad temporal: O(N^2) 
Espacio auxiliar : O(N^2) 

Consulte el artículo completo sobre Inserciones mínimas para formar un palíndromo | DP-28 para más detalles!