以最少的插入次数将字符串转换为回文字符串 [英] Convert string to palindrome string with minimum insertions

问题描述

为了找到将给定字符串转换为回文式所需的最小插入次数，我找到了字符串(lcs_string)及其反向的最长公共子序列.因此，要插入的次数是长度(s)-长度(lcs_string)

In order to find the minimal number of insertions required to convert a given string(s) to palindrome I find the longest common subsequence of the string(lcs_string) and its reverse. Therefore the number of insertions to be made is length(s) - length(lcs_string)

在知道要插入的数目后，应采用什么方法来找到等效的回文字符串?

What method should be employed to find the equivalent palindrome string on knowing the number of insertions to be made?

例如:

1)azbzczdzez

1) azbzczdzez

需要插入的次数:5 回文字符串:azbzcezdzeczbza

Number of insertions required : 5 Palindrome string : azbzcezdzeczbza

虽然同一条字符串可能存在多个回文字符串，但我只想找到一个回文字符串?

Although multiple palindrome strings may exist for the same string but I want to find only one palindrome?

推荐答案

让S[i, j]表示字符串S的子字符串，从索引i开始到索引j(包括两端)和c[i, j]是S[i, j]的最佳解决方案.

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

很明显，c[i, j] = 0 if i >= j.

通常，我们会再次出现:

In general, we have the recurrence:

这篇关于以最少的插入次数将字符串转换为回文字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！