Как я могу вычислить количество символов, необходимых для превращения строки в палиндром?

Ответ 1

Примечание. Это просто любопытство. Дав предложил алгоритм, который может быть модифицирован для алгоритма DP, чтобы работать в O (n ^ 2) времени и O (n ^ 2) пространство легко (и, возможно, O (n) с лучшей бухгалтерией).

Конечно, этот "наивный" алгоритм может пригодиться, если вы решите изменить разрешенные операции.

Вот "наивный" алгоритм, который, вероятно, можно сделать быстрее с умной бухгалтерией.

Учитывая строку, мы предполагаем середину полученного палиндрома, а затем попытаемся вычислить количество вставок, необходимых для создания строки палиндрома вокруг этой середины.

Если строка имеет длину n, существует 2n + 1 возможных средних (каждый символ, между двумя символами, непосредственно перед и сразу после строки).

Предположим, что мы рассмотрим середину, которая дает нам две строки L и R (одна слева и одна справа).

Если мы используем вставки, я считаю, что алгоритм Longest Common Subsequence (который является алгоритмом DP) теперь можно использовать для создания ' супер ", которая содержит как L, так и обратную сторону R, см. Кратчайшая общая суперсимметрия.

Выберите середину, которая даст вам наименьшие числовые вставки.

Это O (n ^ 3) Я считаю. (Примечание: я не пытался доказать, что это правда).

Ответ 2

Решение My С# ищет повторяющиеся символы в строке и использует их для уменьшения количества вставок. В слове, подобном программе, я использую символы "r" в качестве границы. Внутри "r" я делаю палиндром (рекурсивно). За пределами "r" я отражаю символы слева и справа.

Некоторые входы имеют более одного кратчайшего выхода: выход может быть отключен или выведен из строя. Мое решение только выбирает одну из возможностей.

В некоторых примерах выполняется:

• радар → радар, 0 вставок
• esystem → metsystem, 2 вставки
• сообщение → 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;
}

Затем мне нужно найти любые повторяющиеся символы на входе. Их может быть больше одного. Словосочетание имеет два наиболее повторяющихся символа ('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;
    }
}

Обратите внимание, что вам нужна функция Reverse:

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

Ответ 3

С# Рекурсивное решение, добавляющее в конец строки:

Существует 2 базовых варианта. Когда длина равна 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];
        }
    }