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.
Let the input string be str[l……h]. The problem can be broken down into three parts:
1. Find the minimum number of insertions in the substring str[l+1,…….h].
2. Find the minimum number of insertions in the substring str[l…….h-1].
3. Find the minimum number of insertions in the substring str[l+1……h-1].
Time complexity: O(N^2)
Auxiliary Space: O(N^2)
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’.
Read full article from 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.
Let the input string be str[l……h]. The problem can be broken down into three parts:
1. Find the minimum number of insertions in the substring str[l+1,…….h].
2. Find the minimum number of insertions in the substring str[l…….h-1].
3. Find the minimum number of insertions in the substring str[l+1……h-1].
Time complexity: O(N^2)
Auxiliary Space: O(N^2)
// A DP function to find minimum number of insersions
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];
}
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’.
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));
}
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);
}