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/
相关推荐
c语言入门 c语言_1312_minimum_insertion_steps_to_make_a_string_palindrome
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
转变为字符串回文的次数--java-easy- 给定字符串输入,程序将打印回文所需的班次数。 移位是在字符串的一端删除或插入一个字符,然后将其插入到字符串的另一端。 输入格式: 第一行-输入的字符串数为n。...
std::string preprocess(const std::string &str) { std::string result; for (char c : str) { if (std::isalnum(c)) { result += std::tolower(c); } } return result; } bool isPalindrome(std::string ...
《回文:数据结构的魅力与应用》 回文,这个看似简单的词汇,实则蕴含了丰富的数学和计算机科学内涵。在中文中,回文是指正读反读都能保持相同的词语,如“上海自来水来自海上”。而在计算机领域,尤其是数据结构中...
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 ...
JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构
《LeetCode9:判断回文数——Java实现详解》 在编程的世界里,LeetCode是一个广受欢迎的在线平台,它提供了各种算法问题供程序员们挑战和提升技能。今天我们要探讨的是LeetCode第9题——“回文数”。...
回文数Java
PalindromeNumber.java
palindrome22.in
北大POJ1159-Palindrome
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
palindrome_prime.c
标题中的“huiwenshu.rar_palindrome”表明这是一个关于回文数的程序或代码库,可能用于教学或练习目的。回文数是指正向读和反向读都一样的数字,比如121、12321等。在银行管理场景中,回文数可能与账户编号、交易...
Palindrome.py
LeetCode Palindrome Number解决方案 在本节中,我们将讨论如何确定一个整数是否是一个回文数。一个整数是一个回文数当它从左到右读取和从右到左读取相同。 问题描述: 给定一个整数,判断它是否是一个回文数。 ...