Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Eg :-
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
Dynamic Programming based Solution
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 indicates overlapping 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)
Let S[i, j]
represents a sub-string of string S
starting from index i
and ending at index j
(both inclusive) and c[i, j]
be the optimal solution for S[i, j]
.
Obviously, c[i, j] = 0 if i >= j
.
In general, we have the recurrence:
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’.
From:
http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/
相关推荐
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
转变为字符串回文的次数--java-easy- 给定字符串输入,程序将打印回文所需的班次数。 移位是在字符串的一端删除或插入一个字符,然后将其插入到字符串的另一端。 输入格式: 第一行-输入的字符串数为n。...
北大POJ1159-Palindrome 解题报告+AC代码
各位帮帮忙吧
C++实现的Palindrome,回文 C++实现的Palindrome,回文
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
Given a 2-D array of N rows and M columns, your task is to find a maximum sub-array of P rows and P columns, of which each row and each column is a palindrome sequence. Input The first line of ...
Display string by fedi boi palindrome with c
回文数Java
palindrome22.in
北大POJ1159-Palindrome
Best Time to Buy and Sell Stock with Cooldown Interleaving String Scramble String Minimum Path Sum Edit Distance Decode Ways Distinct Subsequences Word Break Word Break II Dungeon Game House Robber ...
GET /java-palindrome-example/palindrome/<string> 解析提供的字符串,并找到其中包含的最大回文。 在此情况下,也可以将type的可选查询参数设置为slow在这种情况下,服务将使用慢得多的递归算法。 例子 GET /java...
回文探测器通过遵循迈克尔·哈特尔... String类的方法,可以如下使用: $ irb>> require 'bencreating_palindrome'>> "honey badger".palindrome?=> false>> "deified".palindrome?=> true>> "Able was I, ere I
LeetCode Palindrome Number解决方案
palindrome_prime.c
Palindrome.py
9.Palindrome Number 10.String To Integer 11.Container With Most Water 12.Integer To Roman 13.Roman To Integer 289 347 380 442 457 Circular Array Loop 535 Encode and Decode TinyURL 560 565 566 Maximum ...
检查字符串是否为palindrome, 从前后分别检查,并计算出相同或不同的数量。