Является ли количество символов, которое нужно удалить, и количество символов, которое нужно добавить, чтобы сделать строку палиндромом равной? - PullRequest
Новая
       34

Является ли количество символов, которое нужно удалить, и количество символов, которое нужно добавить, чтобы сделать строку палиндромом равной?

1 голос
/ 27 апреля 2020

Я прошел 2 вопроса - 1. Найти минимальное количество вставок, необходимое для создания струнного палиндрома? 2. Найти минимальное количество удалений, необходимое для создания строкового палиндрома?

Когда я подошел к нему рекурсивно, оба рекуррентных отношения были одинаковыми, например - «abcda» Вставки 2 (adcbcda), Удаления 2 (aca) 

int minCharsToDeletePalindrome(const string& str, int lo, int hi) {
    if (lo == hi) {
        // Single character is always a palindrome
        return 0;
    }

    if (hi == lo + 1) {
        if (str[lo] == str[hi]) {
            return 0;
        }
        // This means there are only characters left now, 2 chars always need only 1 character to delete such they 
        // become a palindrome.
        return 1;
    }

    if (str[lo] == str[hi]) {
        return minCharsToDeletePalindrome(str, lo + 1, hi - 1);
    }
    else {
        // Added one because we have already deleted one character in both the cases.
        return min(minCharsToDeletePalindrome(str, lo, hi - 1)
            , minCharsToDeletePalindrome(str, lo + 1, hi)) + 1;
    }
}

Логически выглядящие они должны быть равны , поскольку удаляемые символы - это символы, которые препятствуют превращению строки в палиндром и, следовательно, если я добавлю те же символы в строку тогда строка должна стать палиндромом, или я могу пойти другим путем.

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

1 Ответ

0 голосов
/ 27 апреля 2020

Они всегда будут равны. Пусть S будет входной строкой, а P будет палиндромом, который вы сделаете, добавив k символов, где k - это минимальное значение, где это возможно. Найти отражения этих k сложений в P (симметрия c поперек центра P). Удаление этих отражений из S приводит к палиндрому. Таким образом, min_deletions <= min_insertions. Если щелкнуть аргумент, получим min_insertions <= min_deletions, поэтому они должны быть равны. </p>

EG, скажем, исходная строка AXBYA. Минимальное количество вставок - 2: AX (Y) BY (X) A, вставки в скобках. Минимальное удаление 2: ABA, где мы удаляем отражения двух букв, которые мы вставили.

...