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.
-- There is O(N) solution to solve this: based on count of each character.
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].
Recursive Solution
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
http://www.geeksforgeeks.org/remove-character-string-make-palindrome/
http://codegolf.stackexchange.com/questions/25279/remove-a-letter-to-make-a-palindrome
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.
-- There is O(N) solution to solve this: based on count of each character.
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].
// 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];
}
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
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):
findMinInsertions(str, l + 1, h)) + 1);
}
http://www.geeksforgeeks.org/remove-character-string-make-palindrome/
Given a string, we need to check whether it is possible to make this string a palindrome after removing exactly one character from this.
We can solve this problem by finding the position of mismatch. We start looping in the string by keeping two pointers at both the ends which traverse towards mid position after each iteration, this iteration will stop when we find a mismatch, as it is allowed to remove just one character we have two choices here,
At mismatch, either remove character pointed by left pointer or remove character pointed by right pointer.
We will check both the cases, remember as we have traversed equal number of steps from both sides, this mid string should also be a palindrome after removing one character, so we check two substrings, one by removing left character and one by removing right character and if one of them is palindrome then we can make complete string palindrome by removing corresponding character, and if both substrings are not palindrome then it is not possible to make complete string a palindrome under given constraint.
bool
isPalindrome(string::iterator low, string::iterator high)
{
while
(low < high)
{
if
(*low != *high)
return
false
;
low++;
high--;
}
return
true
;
}
// This method returns -1 if it is not possible to make string
// a palindrome. It returns -2 if string is already a palindrome.
// Otherwise it returns index of character whose removal can
// make the whole string palindrome.
int
possiblePalinByRemovingOneChar(string str)
{
// Initialize low and right by both the ends of the string
int
low = 0, high = str.length() - 1;
// loop untill low and high cross each other
while
(low < high)
{
// If both characters are equal then move both pointer
// towards end
if
(str[low] == str[high])
{
low++;
high--;
}
else
{
/* If removing str[low] makes the whole string palindrome.
We basically check if substring str[low+1..high] is
palindrome or not. */
if
(isPalindrome(str.begin() + low + 1, str.begin() + high))
return
low;
/* If removing str[high] makes the whole string palindrome
We basically check if substring str[low+1..high] is
palindrome or not. */
if
(isPalindrome(str.begin() + low, str.begin() + high - 1))
return
high;
return
-1;
}
}
// We reach here when complete string will be palindrome
// if complete string is palindrome then return mid character
return
-2;
}
http://codegolf.stackexchange.com/questions/19381/find-the-longest-palindrome-in-a-string-by-removing-characters
public static String calc(String s) {
if (s.length() == 0)
return "";
if (s.length() == 1 || (s.length() == 2 && s.charAt(0) != s.charAt(1)))
return s.charAt(0) + "";
if (s.length() == 2)
return s;
char[] arr = s.toCharArray();
boolean match = false;
int i = 0;
for (i = arr.length - 1; i > 0; i--) {
if (arr[i] == arr[0]) {
match = true;
break;
}
}
int max = 0;
String maxPalin = "";
for (int k = 1; k < i; k++) {
String p = calc(s.substring(k, i));
if (p.length() > max) {
max = p.length();
maxPalin = p;
}
}
if (match)
return arr[0] + maxPalin + arr[0];
return maxPalin;
}
}
http://isharemylearning.blogspot.com/2012/08/minimum-number-of-insertions-in-string.htmlRead full article from Dynamic Programming | Set 28 (Minimum insertions to form a palindrome) - GeeksforGeeks