如何计算将一个字符串转换为回文所需的字符数？

Question

最近我找到了一个竞赛问题，它要求计算将字符串转换为回文串所需插入的最少字符数（可以在任何位置插入）。

例如，给定字符串："abcbd"，我们可以通过仅插入两个字符来将其变成回文串：在 "a" 后面插入一个字符，在 "d" 后面插入另一个字符："adbcbda"。

这似乎是类似的问题的推广，只不过这个问题只允许在末尾添加字符 - 这有一个相当简单的解决方案，使用哈希表可以在O(N)的时间内完成。

我一直在尝试修改Levenshtein距离算法来解决这个问题，但一直没有成功。任何动态规划（DP）解决方法都可以，我对此很感兴趣，谢谢帮助。

- IVlad

---

@IVlad - 好问题。我已经删除了介绍部分，并添加了一个链接到Levenshtein的维基百科文章。希望这样可以接受。欢迎来到Stack Overflow！ - Dominic Rodger

我忘了问，这是作业吗？ - Aryabhatta

不是作业。这是我国几年前计算机科学奥林匹克竞赛中提出的一个问题，我对解决方案感到兴趣，因为我找不到官方答案，也无法自己想出 DP 算法。 - IVlad

请看我在这里回答一个非常类似的问题： https://dev59.com/ZXbZa4cB1Zd3GeqPI7MC#18758991 它使用了DP方法。 - Piotr Kołaczkowski

Answer 1

注意：这只是一个好奇心。Dav提出了一种算法，可以修改为DP算法，在O(n^2)时间和O(n^2)空间内轻松运行（也许通过更好的簿记可以在O(n)内完成）。

当然，如果您决定更改允许的操作，这个“天真”的算法实际上可能会有用。

---

这是一个“朴素”的算法，可能可以通过巧妙的记账使其更快。

给定一个字符串，我们猜测回文的中间部分，然后尝试计算在该中心周围使字符串成为回文所需的插入次数。

如果字符串的长度为n，则有2n + 1个可能的中间位置（每个字符，两个字符之间，刚好在字符串之前和之后）。

假设我们考虑一个中心，它给出了两个字符串L和R（一个在左边，一个在右边）。

如果我们使用插入，我相信最长公共子序列算法（一种DP算法）现在可以用来创建一个包含L和R的“超级”字符串，参见最短公共超序列。

选择使您需要的插入次数最少的中心。

我相信这是O（n ^ 3）。 （注意：我没有尝试证明它是否正确）。

- Aryabhatta

---

你如何使用SCS来找出如果以字符k为中心排列回文需要多少插入次数呢？以我的例子“abcbd”为例。假设我们以第二个“b”为中心。在“abc”和“d”之间的SCS是“abcd”。这如何告诉你需要插入多少个字符？我认为应该是2*strlen(SCS) - strlen(L) - strlen(R)，这正确吗？ - IVlad

Answer 2

我的C#解决方案查找字符串中重复的字符并利用它们来减少插入的数量。在像program这样的单词中，我使用'r'字符作为边界。在'r'内部，我使其成为回文（递归）。在'r'之外，我将左右两侧的字符镜像。

某些输入具有多个最短输出：output可以是toutptuot或outuputuo。我的解决方案只选择其中一个可能性。

一些示例运行：

• radar -> radar，0插入
• esystem -> metsystem，2插入
• message -> megassagem，3插入
• stackexchange -> stegnahckexekchangets，8插入

首先，我需要检查输入是否已经是回文：

public static bool IsPalindrome(string str)
{
    for (int left = 0, right = str.Length - 1; left < right; left++, right--)
    {
        if (str[left] != str[right])
            return false;
    }
    return true;
}

然后我需要在输入中查找任何重复的字符。可能会有多个。单词message有两个最常重复的字符（'e'和's'）：

private static bool TryFindMostRepeatedChar(string str, out List<char> chs)
{
    chs = new List<char>();
    int maxCount = 1;

    var dict = new Dictionary<char, int>();
    foreach (var item in str)
    {
        int temp;
        if (dict.TryGetValue(item, out temp))
        {
            dict[item] = temp + 1;
            maxCount = temp + 1;
        }
        else
            dict.Add(item, 1);
    }

    foreach (var item in dict)
    {
        if (item.Value == maxCount)
            chs.Add(item.Key);
    }

    return maxCount > 1;
}

我的算法在这里：

public static string MakePalindrome(string str)
{
    List<char> repeatedList;
    if (string.IsNullOrWhiteSpace(str) || IsPalindrome(str))
    {
        return str;
    }
    //If an input has repeated characters,
    //  use them to reduce the number of insertions
    else if (TryFindMostRepeatedChar(str, out repeatedList))
    {
        string shortestResult = null;
        foreach (var ch in repeatedList) //"program" -> { 'r' }
        {
            //find boundaries
            int iLeft = str.IndexOf(ch); // "program" -> 1
            int iRight = str.LastIndexOf(ch); // "program" -> 4

            //make a palindrome of the inside chars
            string inside = str.Substring(iLeft + 1, iRight - iLeft - 1); // "program" -> "og"
            string insidePal = MakePalindrome(inside); // "og" -> "ogo"

            string right = str.Substring(iRight + 1); // "program" -> "am"
            string rightRev = Reverse(right); // "program" -> "ma"

            string left = str.Substring(0, iLeft); // "program" -> "p"
            string leftRev = Reverse(left); // "p" -> "p"

            //Shave off extra chars in rightRev and leftRev
            //  When input = "message", this loop converts "meegassageem" to "megassagem",
            //    ("ee" to "e"), as long as the extra 'e' is an inserted char
            while (left.Length > 0 && rightRev.Length > 0 && 
                left[left.Length - 1] == rightRev[0])
            {
                rightRev = rightRev.Substring(1);
                leftRev = leftRev.Substring(1);
            }

            //piece together the result
            string result = left + rightRev + ch + insidePal + ch + right + leftRev;

            //find the shortest result for inputs that have multiple repeated characters
            if (shortestResult == null || result.Length < shortestResult.Length)
                shortestResult = result;
        }

        return shortestResult;
    }
    else
    {
        //For inputs that have no repeated characters, 
        //  just mirror the characters using the last character as the pivot.
        for (int i = str.Length - 2; i >= 0; i--)
        {
            str += str[i];
        }
        return str;
    }
}

请注意，您需要一个反转函数：

public static string Reverse(string str)
{
    string result = "";
    for (int i = str.Length - 1; i >= 0; i--)
    {
        result += str[i];
    }
    return result;
}

- user2023861

Answer 3

C# 递归解决方案将字符串添加到末尾：

有两个基本情况。当长度为1或2时。递归情况：如果极端相等，则使内部字符串成为回文，不包括极端，并将其与极端一起返回。 如果极端不相等，则将第一个字符添加到末尾，并使包括先前的最后一个字符在内的内部字符串成为回文。返回那个。

public static string ConvertToPalindrome(string str) // By only adding characters at the end
    {
        if (str.Length == 1) return str; // base case 1
        if (str.Length == 2 && str[0] == str[1]) return str; // base case 2
        else
        {
            if (str[0] == str[str.Length - 1]) // keep the extremes and call                
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 2)) + str[str.Length - 1];
            else //Add the first character at the end and call
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 1)) + str[0];
        }
    }

- Ernesto Cejas