Как вычислить количество символов, необходимое для превращения строки в палиндром?
-
19-09-2019 - |
Вопрос
Недавно я нашел задачу конкурса, в которой вас просят вычислить минимальное количество символов, которые необходимо вставить (в любое место) в строку, чтобы превратить ее в палиндром.
Например, учитывая строку:«abcbd» мы можем превратить его в палиндром, вставив всего два символа:один после «а» и другой после «d»:"адBCBDа".
Кажется, это обобщение аналогичной проблемы, которая требует того же самого, за исключением того, что символы можно добавлять только в конце - это довольно простое решение в O (N) с использованием хеш-таблиц.
Я пытался изменить Алгоритм расстояния Левенштейна решить эту проблему, но безуспешно.Любая помощь в том, как решить эту проблему (она не обязательно должна быть эффективной, меня просто интересует любое решение DP) будет оценена по достоинству.
Решение
Примечание:Это просто любопытство.Дэв предложил алгоритм, который можно модифицировать в алгоритм DP, чтобы он мог легко работать за время O(n^2) и в пространстве O(n^2) (и, возможно, за O(n) с лучшим ведением бухгалтерского учета).
Конечно, этот «наивный» алгоритм может пригодиться, если вы решите изменить разрешенные операции.
Вот «наивный» алгоритм, который, вероятно, можно сделать быстрее с помощью умного бухгалтерского учета.
Учитывая строку, мы угадываем середину полученного палиндрома, а затем пытаемся вычислить количество вставок, необходимых для того, чтобы строка стала палиндромом вокруг этой середины.
Если строка имеет длину n, существует 2n+1 возможных средних значений (каждый символ между двумя символами, непосредственно перед и сразу после строки).
Предположим, мы рассматриваем середину, которая дает нам две строки L и R (одну слева и одну справа).
Если мы используем вставки, я считаю, что Самая длинная общая подпоследовательность Алгоритм (который является алгоритмом DP) теперь можно использовать для создания «супер» строки, которая содержит как L, так и обратную букву R, см. Кратчайшая общая суперпоследовательность.
Выберите середину, которая даст вам наименьшее количество вставок.
Я считаю, что это O(n^3).(Примечание:Я не пытался доказать, что это правда).
Другие советы
Мое решение на C# ищет повторяющиеся символы в строке и использует их для уменьшения количества вставок.Одним словом как программа, я использую символы «r» в качестве границы.Внутри буквы «r» я делаю палиндром (рекурсивно).За пределами буквы «r» я зеркально отображаю символы слева и справа.
Некоторые входы имеют более одного кратчайшего выхода: выход возможно рекламировать или вывод.Мое решение выбирает только одну из возможностей.
Некоторые примеры:
- радар -> радар, 0 вставок
- система -> метсистема, 2 вставки
- сообщение -> мегасагем, 3 вставки
- обмен стеками -> Стегнахкексекханчец, 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;
}
С# Рекурсивное решение, добавляющее в конец строки:
Есть 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];
}
}