要删除的字符数和要添加的字符数是否相等？

Question

我通过了两个问题-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;
    }
}

从逻辑上看，它们应该是相等的，因为要删除的字符是阻止字符串成为回文的字符，因此如果我将相同的字符添加到字符串中，那么字符串应该成为回文，或者我可以用其他方法。

那么，我的推断是否正确，或者是否有任何情况下，它们是不相等的？

Answer 1

他们永远是平等的。设S为输入字符串，P为通过添加k个字符生成的回文，其中k为可能的最小值。求这些k加法在P中的反射（在P的中心对称）。从S中删除这些反射将产生回文。因此，min_删除

例如，假设原始字符串是AXBYA。插入的最小数量为2:AX（Y）乘（X）A，插入以parens为单位。最小删除量为2:ABA，其中删除插入的两个字母的反射。