字符串转换为字符串回文最小插入(Convert string to palindrome strin

为了找到一个给定的字符串（S）转换为回文需要插入的最少数量我查找的字符串（lcs_string）和其反向的最长公共子。 因此插入的要进行的数是长度（S） - 长度（lcs_string）

用什么方法应采用以找到了解插入的数目相当于回文字符串进行？

例如 ：

1）azbzczdzez

需要插入数量：5回文字符串：azbzcezdzeczbza

尽管多个回文字符串可能存在相同的字符串，但我想找到只有一个回文？

Answer 1:

让S[i, j]表示串的子串S从索引开始i并在索引结束j （包括两端）和c[i, j]为最优解S[i, j]

显然， c[i, j] = 0 if i >= j 。

在一般情况下，我们有复发：

Answer 2:

细说VenomFangs答案，有一个简单的动态规划解决这一个。 请注意，我假设这里唯一允许的操作字符（不删除，更新）的插入。 设S是n个字符的字符串。 这个简单的递归函数P是：

    = P [i+1 .. j-1], if S[i] = S[j] 

P [i..j]

    = min (P[i..j-1], P[i+1..j]) + 1,

如果您想为什么这是真的更多的解释，发表评论，我很乐意解释（虽然它很容易与花点心思看到）。 这，顺便说一句，是LCS的完全相反的功能，您使用的，因此验证您的解决方案，其实是最佳的。 当然，其全资可能我砸，如果是这样，有人不要让我知道！

编辑：要占回文本身，这可以轻松完成如下：如上所述，P [1..1]会给你做出这个字符串回文需要插入的数目。 一旦上述二维数组是建起来了，这里是你如何找到回文：

开始以i = 1，J = N。 现在，串输出=“”;

while(i < j)
{
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point
    {
        output = output + S[i];
        i++;
        j--;
    }
    else
    if (P[i][j] == P[i+1][j]) //
    {
        output = output + S[i];
        i++;
    }
    else
    {
        output = S[j] + output;
        j--;
    }
 }
 cout<<output<<reverse(output);
 //You may have to be careful about odd sized palindromes here,
 // I haven't accounted for that, it just needs one simple check

这是否让更好的阅读？

Answer 3:

该解决方案看起来是一个动态规划的解决方案。

您可以找到以下后您的答案： 我该如何计算的字符将一个字符串变成回文需要多少？

Answer 4:

的O PHP求解（n）

function insertNode(&$arr, $idx, $val) {
    $arr = array_merge(array_slice($arr, 0, $idx), array($val), array_slice($arr, $idx));
}
function createPalindrome($arr, $s, $e) {
    $i = 0;
    while(true) {
        if($s >= $e) {
            break;
        } else if($arr[$s] == $arr[$e]) {
            $s++; $e--; // shrink the queue from both sides 
            continue;
        } else {
            insertNode($arr, $s, $arr[$e]);
            $s++;
        }
    }
    echo implode("", $arr);
}
$arr = array('b', 'e', 'a', 'a', 'c', 'd', 'a', 'r', 'e');
echo createPalindrome ( $arr, 0, count ( $arr ) - 1 );

Answer 5:

简单。 见下文 ：）

        String pattern = "abcdefghgf";
        boolean isPalindrome = false;
        int i=0,j=pattern.length()-1;
        int mismatchCounter = 0;

        while(i<=j)
        {
            //reverse matching
            if(pattern.charAt(i)== pattern.charAt(j))
                {
                    i++; j--; 
                    isPalindrome = true;
                    continue;
                }

            else if(pattern.charAt(i)!= pattern.charAt(j))
                {
                    i++;
                    mismatchCounter++;
                }


        }
        System.out.println("The pattern string is :"+pattern);
        System.out.println("Minimum number of characters required to make this string a palidnrome : "+mismatchCounter);

文章来源: Convert string to palindrome string with minimum insertions