Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
Before we go further, let us understand with few examples:
ab: Number of insertions required is 1.bab
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3.dcbabcd
abcda: Number of insertions required is 2. adcbcda which is same as number of insertions in the substring bcd(Why?).
abcde: Number of insertions required is 4.edcbabcde
Let the input string bestr[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
Dynamic Programming based Solution
If we observe the above approach carefully, we can find that it exhibitsoverlapping subproblems.
Suppose we want to find the minimum number of insertions in 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………………….
The substrings in bold show that the recursion to be terminated and the recursion tree cannot originate from there. Substring in the same color indicatesoverlapping
subproblems.
How to reuse solutions of subproblems?
We can create a table to store results of subproblems so that they can be used directly if same subproblem is encountered again.
The below table represents the stored values for the 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
How to fill the table?
The table should be filled in diagonal fashion. For the string abcde, 0….4, the following should be order in which the table is filled:
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)
Another Dynamic Programming Solution (Variation ofLongest
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’.
package DP;
public class MinInsertionsPalindrome {
public static void main(String[] args) {
String s = "geeks";
int l = 0;
int h = s.length()-1;
System.out.println(findMinInsertionsRec(s, l, h));
System.out.println(findMinInsertionsDP(s, s.length()));
System.out.println(findMinInsertionsLCS(s, s.length()));
}
public static int findMinInsertionsRec(String s, int l, int h){
if(l > h){
return Integer.MAX_VALUE;
}
if(l == h){
return 0;
}
if(l+1 == h){
return (s.charAt(l)==s.charAt(h) ? 0 : 1);
}
if(s.charAt(l) == s.charAt(h)){
return findMinInsertionsRec(s, l+1, h-1);
}else{
return Math.min(findMinInsertionsRec(s, l+1, h), findMinInsertionsRec(s, l, h-1)) + 1;
}
}
// Time complexity: O(N^2) Auxiliary Space: O(N^2)
public static int findMinInsertionsDP(String s, int n){
int[][] dp = new int[n][n];
for(int gap=1; gap<n; gap++){ // gap: l到h之间的距离
int l = 0, h = gap;
while(h < n){ // 平行移动l...h
if(s.charAt(l) == s.charAt(h)){
dp[l][h] = dp[l+1][h-1];
}else{
dp[l][h] = Math.min(dp[l+1][h], dp[l][h-1]) + 1;
}
l++;
h++;
}
}
return dp[0][n-1];
}
// Time complexity: O(N^2) Auxiliary Space: O(N^2)
public static int findMinInsertionsLCS(String s, int n){
// Create another string to store reverse of 'str'
String rev = new StringBuilder(s).reverse().toString();
// The output is length of string minus length of lcs of
// str and it reverse
return n - lcs(s, rev, n, n);
}
/* Returns length of LCS for X[0..m-1], Y[0..n-1].
See http://goo.gl/bHQVP for details of this function */
public static int lcs(String X, String Y, int m, int n){
int[][] L = new int[m+1][n+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(int i=0; i<=m; i++){
for(int j=0; j<=n; j++){
if(i==0 || j==0){ // 空string
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] = Math.max(L[i-1][j], L[i][j-1]);
}
}
}
return L[m][n]; /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/
分享到:
相关推荐
资源--回文字符串
C++实现的Palindrome,回文 C++实现的Palindrome,回文
顺序读入一个字符串数据(不含空格),判断能否将串中字符重新组合可以构成一个回文串。如用lvele可以构成回文串level、elvle,而用label则无法构成回文串。
计算10000以内回文数的个数,回文数也叫做回旋数,就是正着读和反过来读是一样的
可实现三种功能: (1)判断一整个字符串是否为回文; (2)判断指定位置的子串是否为回文; (3)输出此字符串中最长的子字符串;
所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的。回文数字也是如此。 python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False ...
回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数
//第一个循环,输入数组a for (i = 0; i ; i++) { a[i] = char.Parse(Console.ReadLine()); //Console.WriteLine(a[i]); } //第二个循环,输出数组a for (i = 0; i ; i++) Console.Write(a[i] + " "); //...
Python实现最短回文字符串输出
例如6886就是一个回文数,求出所有的既是回文数又是素数的三位数。 【输入】 (无) 【输出】 所有的既是回文数又是素数的三位数。一个数一行。 【输入样例】 (无) 【输出样例】 (无) 【来源】 No
回文串是从左到右读与从右到左读字符方式一样的一个字符串,如ABCBA、eluparcettecrapule是回文串,但123431不是回文串。 编一个程序判断一个串是否为回文串。 键盘输入一个以回车结尾的字符串STR,如果是回文串,...
解决JAVA语言中的回文数和猜数字的问题
1.任意输入一个数,用两种方法判断该数是不是回文数,像1,323,45254; 方法一,设原数为12,是将输入数进行倒序(21),然后与原数(12)进行比较,若不同则不是回文;...任意输入一个字符串,判断它是不是一个回文字符串
# 给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。 # 如果存在,则输出YES,否则输出NO。 # 回文串的定义:记串str逆序之后的字符串是str1,若str=str1,则称str是回文串,如"abcba". # 输入...
java编的回文显示回文字符串的一个方法,例如abc会输出abcba。
编写一个Java应用程序。用户从键盘输入一个1~99999之间的数,程序将判断这个数是几位数,并判断这个数是否是回文数。回文数是指将该数含有的数字逆序排列后得到的数和原数相同,如12121和3223都是回文数
本程序可以判断字符串是否回文,在程序运行时输入所要判断的字符串,按回车后将输出是或不是回文。
查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)
c语言代码写的回文字符串判断, for(i=0;i;) { if(str[i++]!=str[j--]) return 0;
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。