Dynamic Programming | Set 28 (Minimum insertions to form a palindrome) | GeeksforGeeks

Dynamic Programming | Set 28 (Minimum insertions to form a palindrome) | GeeksforGeeks
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.

The minimum number of insertions in the string str[l…..h] can be given as:
minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise

int findMinInsertionsDP(char str[], int n)

{

    // Create a table of size n*n. table[i][j] will store

    // minumum 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];

}

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

}

Another Dynamic Programming Solution (Variation of Longest Common Subsequence Problem)The problem of finding minimum insertions can also be solved using Longest Common Subsequence (LCS) Problem. If we find out LCS of string and its reverse, we know how many maximum characters can form a palindrome. We need insert remaining characters. Following are the steps.
1) Find the length of LCS of input string and its reverse. Let the length be ‘l’.
2) The minimum number insertions needed is length of input string minus ‘l’.
http://isharemylearning.blogspot.com/2012/08/minimum-number-of-insertions-in-string.html
Solution: Take any string, for e.g. “SARGAM”. This is not palindrome but if you delete the characters 'S', 'G', 'M' what remains is “ARA” and this is palindrome. Now this palindrome was already in the given string and its length is three. So basically we've to find out the length of longest palindrome which is already hidden inside in given string. In this way, our

/* 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[n+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 insersions

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

}

Related: Longest palindrom by deleting/inserting elements
Read full article from Dynamic Programming | Set 28 (Minimum insertions to form a palindrome) | GeeksforGeeks