`

[待续]Convert string to palindrome string with minimum insertions

阅读更多

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:

enter image description here 

 

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/

http://stackoverflow.com/questions/10729282/convert-string-to-palindrome-string-with-minimum-insertions

分享到:
评论

相关推荐

    c语言-1312-minimum-insertion-steps-to-make-a-string-palindrome

    c语言入门 c语言_1312_minimum_insertion_steps_to_make_a_string_palindrome

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    Number-of-shifts-left-to-right-and-vice-versa-to-make-a-string-palindrome.-java-easy-:给定字符串输入,程序将打印回文所需的班次数

    转变为字符串回文的次数--java-easy- 给定字符串输入,程序将打印回文所需的班次数。 移位是在字符串的一端删除或插入一个字符,然后将其插入到字符串的另一端。 输入格式: 第一行-输入的字符串数为n。...

    C++实现的Palindrome,回文

    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 ...

    palindrome

    《回文:数据结构的魅力与应用》 回文,这个看似简单的词汇,实则蕴含了丰富的数学和计算机科学内涵。在中文中,回文是指正读反读都能保持相同的词语,如“上海自来水来自海上”。而在计算机领域,尤其是数据结构中...

    Pku acm 第1159题 Palindrome 代码

    Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划

    Palindrome Sub-Array

    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程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构

    LeetCode9 Palindrome Number

    《LeetCode9:判断回文数——Java实现详解》 在编程的世界里,LeetCode是一个广受欢迎的在线平台,它提供了各种算法问题供程序员们挑战和提升技能。今天我们要探讨的是LeetCode第9题——“回文数”。...

    Palindrome.java

    回文数Java

    PalindromeNumber.java

    PalindromeNumber.java

    palindrome22.in

    palindrome22.in

    北大POJ1159-Palindrome

    北大POJ1159-Palindrome

    java-palindrome-example:一个示例Java服务

    GET /java-palindrome-example/palindrome/&lt;string&gt; 解析提供的字符串,并找到其中包含的最大回文。 在此情况下,也可以将type的可选查询参数设置为slow在这种情况下,服务将使用慢得多的递归算法。 例子 GET /java...

    palindrome:Ruby回文检测器。 通过遵循了解足够的Ruby来进行构建

    回文探测器通过遵循迈克尔·哈特尔... String类的方法,可以如下使用: $ irb&gt;&gt; require 'bencreating_palindrome'&gt;&gt; "honey badger".palindrome?=&gt; false&gt;&gt; "deified".palindrome?=&gt; true&gt;&gt; "Able was I, ere I

    palindrome_prime.c

    palindrome_prime.c

    huiwenshu.rar_palindrome

    标题中的“huiwenshu.rar_palindrome”表明这是一个关于回文数的程序或代码库,可能用于教学或练习目的。回文数是指正向读和反向读都一样的数字,比如121、12321等。在银行管理场景中,回文数可能与账户编号、交易...

    Palindrome.py

    Palindrome.py

    LeetCode Palindrome Number解决方案

    LeetCode Palindrome Number解决方案 在本节中,我们将讨论如何确定一个整数是否是一个回文数。一个整数是一个回文数当它从左到右读取和从右到左读取相同。 问题描述: 给定一个整数,判断它是否是一个回文数。 ...

Global site tag (gtag.js) - Google Analytics