Чтобы найти минимальное количество вставок, необходимых для преобразования данной строки (ов) в палиндром, я нахожу самую длинную общую подпоследовательность строки (lcs_string) и ее обратную. Поэтому число вставок, которое нужно сделать, это length (s) - length (lcs_string)
Какой метод следует использовать для поиска эквивалентной строки палиндрома при знании числа вставок, которые нужно сделать?
Например:
1) azbzczdzez
Требуется количество вставок: 5 Палиндрома: azbzcezdzeczbza
Хотя для одной и той же строки могут существовать несколько строк палиндрома, но я хочу найти только один палиндром?
Пусть S[i, j] представляет подстроку строки S, начиная с индекса i и заканчивая индексом j (оба включительно) и c[i, j] является оптимальным решением для S[i, j].
Очевидно, c[i, j] = 0 if i >= j.
В общем случае мы имеем рекуррентность:
Чтобы уточнить ответ 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..n] даст вам количество вставок, необходимых для создания этой строки палиндрома. После того, как выстроил вышеописанный двумерный массив, вот как вы находите палиндром:
Начнем с я = 1, j = n. Теперь, string output = "";
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
Это улучшает чтение?
Решение выглядит как динамическое программирующее решение.
Вы можете найти свой ответ в следующем сообщении: Как я могу вычислить количество символов, необходимых для превращения строки в палиндром?
PHP Решение O (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 );
Simple. См. Ниже:)
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);