如何以最少的字符串去除次数将字符串转换为回文？ [英] how to convert a string to palindrome with minimum number of removals of characters of the string?
问题描述
假设字符串为 anuja，则输出应为2，因为如果我删除字符 u和 n，则给定的字符串将成为回文。因此，输出应为最小去除次数。
的更多示例：输入字符串： ababa
输出：0（无需删除）
输入字符串： abcdba
输出：1（删除'c'或' d'）
请说明算法。
suppose the string is "anuja", the output should be 2 because if I remove the characters 'u' and 'n', the given string becomes a palindrome.Thus the output should be the minimum number of removals. more examples: input string: "ababa" output: 0 (no removal needed) input string:"abcdba" output: 1 (removal of 'c' or 'd') please explain the algorithm.
推荐答案
让 dp [i，j] =将子字符串[i，j]转换为回文所需的最小移除次数。我们有：
dp[i, i] = 0 for all i (every single character is a palindrome)
要查找 dp [i，j] ，让我们考虑随机字符串。我们有两种可能性：
To find dp[i, j], let's consider a random string. We have two possibilities:
-
第一个和最后一个字符相等：
a [i] == a [j]。在这种情况下，我们可以减少问题，找到需要删除的最小字符数才能使子字符串[i + 1，j-1]a回文。
The first and last characters are equal:
a[i] == a[j]. In this case, we can reduce the problem to finding the minimum number of characters that need to be deleted in order to make the substring[i+1, j-1]a palindrome.
第一个和最后一个字符不相等： a [i]！= a [j] 。在这种情况下，我们需要删除其中之一。我们将删除导致我们找到更好解决方案的内容。
The first and last characters are not equal: a[i] != a[j]. In this case, we need to remove one of them. We'll remove that which leads us to a better solution.
因此我们拥有：
dp[i, j] = dp[i + 1, j - 1] # if a[i] == a[j]
min(dp[i + 1, j], dp[i, j - 1]) + 1 # otherwise
以 anuja 为例。我们会得到：
| 1 2 3 4 5
-------------
1 | 0 1 2 2 2
2 | 0 1 2 3
3 | 0 1 2
4 | 0 1
5 | 0
请注意，矩阵是从主对角线开始计算，然后按顺序向上对角线平行于主对角线。答案是 dp [1，n] 。
Note that the matrix is computed starting with the main diagonal and continuing upwards, in order, with the diagonals parallel to the main diagonal. The answer is dp[1, n].
这类似于Levenshtein距离，但它仅考虑移除。
This is similar to the Levenshtein distance, but it only considers removals.
这篇关于如何以最少的字符串去除次数将字符串转换为回文？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
