Mínimas inserciones para formar un palíndromo | DP-28 – Part 1

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:  

C++

// 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 subproblem(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

C

// A Naive recursive program to find minimum
// number insertions needed to make a string
// palindrome
#include <stdio.h>
#include <limits.h>
#include <string.h>
 
// A utility function to find minimum of two numbers
int min(int a, int b)
{  return a < b ? a : b; }
 
// 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 subproblem(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 program to test above functions
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertions(str, 0, strlen(str)-1));
    return 0;
}

Java

// A Naive recursive Java program to find minimum
// number insertions needed to make a string
// palindrome
class GFG {
 
    // Recursive function to find minimum number
    // of insertions
    static int findMinInsertions(char str[], int l,
                                             int h)
    {
        // Base Cases
        if (l > h) return Integer.MAX_VALUE;
        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 subproblem(s) to call
        return (str[l] == str[h])?
            findMinInsertions(str, l + 1, h - 1):
            (Integer.min(findMinInsertions(str, l, h - 1),
            findMinInsertions(str, l + 1, h)) + 1);
    }
 
    // Driver program to test above functions
    public static void main(String args[])
    {
        String str= "geeks";
        System.out.println(findMinInsertions(str.toCharArray(),
                                          0, str.length()-1));
    }
}
// This code is contributed by Sumit Ghosh

Python 3

# A Naive recursive program to find minimum
# number insertions needed to make a string
# palindrome
import sys
 
# Recursive function to find minimum
# number of insertions
def findMinInsertions(str, l, h):
 
    # Base Cases
    if (l > h):
        return sys.maxsize
    if (l == h):
        return 0
    if (l == h - 1):
        return 0 if(str[l] == str[h]) else 1
 
    # Check if the first and last characters are
    # same. On the basis of the comparison result,
    # decide which subproblem(s) to call
     
    if(str[l] == str[h]):
        return findMinInsertions(str, l + 1, h - 1)
    else:
        return (min(findMinInsertions(str, l, h - 1),
                    findMinInsertions(str, l + 1, h)) + 1)
 
# Driver Code
if __name__ == "__main__":
     
    str = "geeks"
    print(findMinInsertions(str, 0, len(str) - 1))
 
# This code is contributed by ita_c

C#

// A Naive recursive C# program
// to find minimum number
// insertions needed to make
// a string palindrome
using System;
 
class GFG
{
    // Recursive function to
    // find minimum number of
    // insertions
    static int findMinInsertions(char []str,
                                 int l, int h)
    {
        // Base Cases
        if (l > h) return int.MaxValue;
        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 subproblem(s) to call
        return (str[l] == str[h])?
                findMinInsertions(str,
                                  l + 1, h - 1):
                (Math.Min(findMinInsertions(str, l,
                                            h - 1),
                          findMinInsertions(str, l +
                                        1, h)) + 1);
    }
     
    // Driver Code
    public static void Main()
    {
        string str= "geeks";
        Console.WriteLine(findMinInsertions(str.ToCharArray(),
                                            0, str.Length - 1));
    }
}
 
// This code is contributed by Sam007

Javascript

<script>
 
// A Naive recursive JavaScript program to find minimum
// number insertions needed to make a string
// palindrome
 
    // Recursive function to find minimum number
    // of insertions
    function findMinInsertions(str,l,h)
    {
        // Base Cases
        if (l > h)
            return Number.MAX_VALUE;
         
        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 subproblem(s) to call
        return (str[l] == str[h]) ?
        findMinInsertions(str, l + 1, h - 1) :
        (Math.min(findMinInsertions(str, l, h - 1),
        findMinInsertions(str, l + 1, h)) + 1)       
    }
     
    // Driver program to test above functions
    let str= "geeks";
    document.write(findMinInsertions(str,0, str.length-1));
     
     
    // This code is contributed by rag2127
     
</script>
Producción

3

Tiempo Complejidad : O(n n )

Espacio Auxiliar: O(n)

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: 

C++

// 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

C

// A Dynamic Programming based program to find
// minimum number insertions needed to make a
// string palindrome
#include <stdio.h>
#include <string.h>
 
// A utility function to find minimum of two integers
int min(int a, int b)
{   return a < b ? a : b;  }
 
// 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 program to test above function.
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsDP(str, strlen(str)));
    return 0;
}

Java

// A Java solution for Dynamic Programming
// based program to find minimum number
// insertions needed to make a string
// palindrome
import java.util.Arrays;
 
class GFG
{
    // A DP function to find minimum number
    // of insertions
    static 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[][] = new int[n][n];
        int l, h, gap;
 
        // 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] :
                          (Integer.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 program to test above function.
    public static void main(String args[])
    {
        String str = "geeks";
        System.out.println(
        findMinInsertionsDP(str.toCharArray(), str.length()));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# A Dynamic Programming based program to
# find minimum number insertions needed
# to make a string palindrome
 
# A utility function to find minimum
# of two integers
def Min(a, b):
    return min(a, b)
 
# A DP function to find minimum number
# of insertions
def findMinInsertionsDP(str1, n):
 
    # Create a table of size n*n. table[i][j]
    # will store minimum number of insertions
    # needed to convert str1[i..j] to a palindrome.
    table = [[0 for i in range(n)]
                for i in range(n)]
    l, h, gap = 0, 0, 0
 
    # Fill the table
    for gap in range(1, n):
        l = 0
        for h in range(gap, n):
            if str1[l] == str1[h]:
                table[l][h] = table[l + 1][h - 1]
            else:
                table[l][h] = (Min(table[l][h - 1],
                                   table[l + 1][h]) + 1)
            l += 1
 
    # Return minimum number of insertions
    # for str1[0..n-1]
    return table[0][n - 1];
 
# Driver Code
str1 = "geeks"
print(findMinInsertionsDP(str1, len(str1)))
 
# This code is contributed by
# Mohit kumar 29

C#

// A C# solution for Dynamic Programming
// based program to find minimum number
// insertions needed to make a string
// palindrome
using System;
 
class GFG
{
    // A DP function to find minimum number
    // of insertions
    static 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 = new int[n, n];
        int l, h, gap;
 
        // 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] :
                        (Math.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
    public static void Main()
    {
        String str = "geeks";
        Console.Write(
        findMinInsertionsDP(str.ToCharArray(), str.Length));
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// A Javascript solution for Dynamic Programming
// based program to find minimum number
// insertions needed to make a string
// palindrome
 
     
    // A DP function to find minimum number
    // of insertions
    function findMinInsertionsDP(str,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.
         
        let table=new Array(n);
        for(let i=0;i<n;i++)
        {
            table[i]=new Array(n);
        }
         
         
        for(let i=0;i<n;i++)
        {
            for(let j=0;j<n;j++)
            {
                table[i][j]=0;
            }
        }
         
         
        let  l=0, h=0, gap=0;
        // 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] : (Math.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 program to test above function.
    let str = "geeks";
    document.write(findMinInsertionsDP(str, str.length));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>
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:  

C++

// 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

C

// An LCS based program to find minimum number
// insertions needed to make a string palindrome
#include<stdio.h>
#include <string.h>
 
/* Utility function to get max of 2 integers */
int max(int a, int b)
{   return (a > b)? a : b; }
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1].
   See http://goo.gl/bHQVP for details of this
   function */
int lcs( char *X, char *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];
}
 
// LCS based function to find minimum number of
// insertions
int findMinInsertionsLCS(char str[], int n)
{
   // Creata another string to store reverse of 'str'
   char rev[n+1];
   strcpy(rev, str);
   strrev(rev);
 
   // The output is length of string minus length of lcs of
   // str and it reverse
   return (n - lcs(str, rev, n, n));
}
 
// Driver program to test above functions
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsLCS(str, strlen(str)));
    return 0;
}

Java

// An LCS based Java program to find minimum
// number insertions needed to make a string
// palindrome
class GFG
{
    /* Returns length of LCS for X[0..m-1],
       Y[0..n-1]. See http://goo.gl/bHQVP for
       details of this function */
    static int lcs( String X, String Y, int m, int n )
    {
        int L[][] = new int[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.charAt(i-1) == Y.charAt(j-1))
                    L[i][j] = L[i-1][j-1] + 1;
 
                else
                    L[i][j] = Integer.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];
    }
 
    // LCS based function to find minimum number
    // of insertions
    static int findMinInsertionsLCS(String str, int n)
    {
        // Using StringBuffer to reverse a String
        StringBuffer sb = new StringBuffer(str);
        sb.reverse();
        String revString = sb.toString();
 
        // The output is length of string minus
        // length of lcs of str and it reverse
        return (n - lcs(str, revString , n, n));
    }
 
    // Driver program to test above functions
    public static void main(String args[])
    {
        String str = "geeks";
        System.out.println(
        findMinInsertionsLCS(str, str.length()));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# An LCS based Python3 program to find minimum
# number insertions needed to make a string
# palindrome
 
""" Returns length of LCS for X[0..m-1],
Y[0..n-1]. See http://goo.gl/bHQVP for
details of this function """
def lcs(X, Y, m, n) :
 
    L = [[0 for i in range(n + 1)] for j in range(m + 1)]
 
    """ 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 in range(m + 1) :    
        for j in range(n + 1) :      
            if (i == 0 or j == 0) :
                L[i][j] = 0
 
            elif (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]
     
# LCS based function to find minimum number
# of insertions
def findMinInsertionsLCS(Str, n) :
 
    # Using charArray to reverse a String
    charArray = list(Str)
    charArray.reverse()
    revString = "".join(charArray)
     
    # The output is length of string minus
    # length of lcs of str and it reverse
    return (n - lcs(Str, revString , n, n))
 
# Driver code 
Str = "geeks"
print(findMinInsertionsLCS(Str,len(Str)))
 
# This code is contributed by divyehrabadiya07

C#

// An LCS based C# program to find minimum
// number insertions needed to make a string
// palindrome
using System;
 
class GFG
{
    /* Returns length of LCS for X[0..m-1],
    Y[0..n-1]. See http://goo.gl/bHQVP for
    details of this function */
    static int lcs( string X, string Y, int m, int n )
    {
        int[,] L = new int[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] = Math.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];
    }
 
    // LCS based function to find minimum number
    // of insertions
    static int findMinInsertionsLCS(string str, int n)
    {
        // Using charArray to reverse a String
        char[] charArray = str.ToCharArray();
        Array.Reverse(charArray);
        string revString = new string(charArray);
 
        // The output is length of string minus
        // length of lcs of str and it reverse
        return (n - lcs(str, revString , n, n));
    }
 
    // Driver code
    static void Main()
    {
        string str = "geeks";
        Console.WriteLine(findMinInsertionsLCS(str,str.Length));
    }
}
 
// This code is contributed by mits

Javascript

<script>
// An LCS based Javascript program to find minimum
// number insertions needed to make a string
// palindrome
     
    /* Returns length of LCS for X[0..m-1],
       Y[0..n-1]. See http://goo.gl/bHQVP for
       details of this function */
    function lcs(X, Y, m, n)
    {
        let L = new Array(m+1);
        for(let i = 0; i < m + 1; i++)
        {
            L[i] = new Array(n+1);
            for(let j = 0; j < n + 1; j++)
            {
                L[i][j] = 0;
            }
        }
         
        let 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] = Math.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];
    }
     
    // LCS based function to find minimum number
    // of insertions
    function findMinInsertionsLCS(str, n)
    {
        let revString = str.split('').reverse().join('');
         
        // The output is length of string minus
        // length of lcs of str and it reverse
        return (n - lcs(str, revString , n, n));
         
    }
     
    // Driver program to test above functions
    let str = "geeks";
    document.write(findMinInsertionsLCS(str, str.length));
     
    // This code is contributed by unknown2108
</script>
Producción

3

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

Método de optimización de espacio: el código anterior se puede optimizar en el espacio usando solo una array 1d en lugar de una array 2d. En la tabla dp solo necesitamos la fila anterior y los elementos de la fila actual.

C++

// 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)
{
    vector<int> prev(n + 1, 0), curr(n + 1, 0);
    int i, j;
 
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                prev[j] = 0;
 
            else if (X[i - 1] == Y[j - 1])
                curr[j] = prev[j - 1] + 1;
 
            else
                curr[j] = max(prev[j], curr[j - 1]);
        }
       
        prev = curr;
    }
 
    /* L[m][n] contains length of LCS for X[0..n-1]
            and Y[0..m-1] */
    return prev[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 Sanskar

C#

/* C# program to implement an LCS based approach
to find minimum number of insertions needed
to make a string palindrome*/
 
using System;
using System.Collections.Generic;
 
class GFG {
    // Returns length of LCS for X[0..m-1], Y[0..n-1].
    static int Lcs(string X, string Y, int m, int n)
    {
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        int i, j;
 
        for (i = 0; i <= m; i++) {
            for (j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    prev[j] = 0;
 
                else if (X[i - 1] == Y[j - 1])
                    curr[j] = prev[j - 1] + 1;
 
                else
                    curr[j]
                        = Math.Max(prev[j], curr[j - 1]);
            }
 
            prev = curr;
        }
 
        /* L[m][n] contains length of LCS for X[0..n-1]
                and Y[0..m-1] */
        return prev[n];
    }
 
    // LCS based function to find minimum number of
    // insertions
    static int FindMinInsertionsLCS(string str, int n)
    {
        // Creat another string to store reverse of 'str'
        char[] tmp = str.ToCharArray();
        Array.Reverse(tmp);
        string rev = new string(tmp);
 
        // The output is length of string minus length of
        // lcs of str and it reverse
        return (n - Lcs(str, rev, n, n));
    }
 
    // Driver code
    static void Main(string[] args)
    {
        string str = "geeks";
        Console.WriteLine(
            FindMinInsertionsLCS(str, str.Length));
    }
}
// This code is contributed by cavi4762
Producción

3

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

Artículo relacionado: 
Número mínimo de apéndices necesarios para hacer un palíndromo de strings
Este artículo fue compilado por Aarti_Rathi y Aashish Barnwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *