java - 通过删除字符从现有字符串创建回文

Question

我如何通过删除零个或多个字母来确定您可以从一个单词中获得的最长回文的长度。

例如：amanQQQapl12345anacaZZZnalpaXXXna67890ma
最长的回文将是 21 位数字。

Answer 1

这可以通过动态规划来解决。将d[i, j]定义为原始字符串中最长回文的长度。

如果 s[i] = s[j], d[i, j] = max(d[i+1, j-1] + 2, d[i, j-1], d[i+1, j] ）。

否则 d[i, j] = max(d[i, j-1], d[i+1, j])。

Answer 2

单词 W 中最长的回文是W 及其镜像的最长公共子序列。

您可以在 O(n²) 时间和 O(n) 空间中计算它，其中 n 是 W 的长度，但如果您知道只需要删除几个字符来制作回文，则可以有更好的复杂性。

Answer 3

回文最多可以有一个奇数字母，即中间字母，以及任意数量的偶​​数字母。

您可以计算每个字母出现的频率。如果每个字母不是全部或没有，则为每个字母添加计数/2*2，如果任何字母的计数为奇数，则添加一个。

Answer 4

这是@Rambo 答案的正确实现，以防其他人发现他的答案过于简洁。我添加了对先前结果的缓存，但条件是不同符号的最大数量最多为 1000。由于多个分支使用相同的子分支，这提供了显着的加速。

int d[1000][1000] = {0}; // To store result of previous computation

int computeMaxPalindromeLength(vector<int>& a, int start, int end) {
    if(d[start][end] != 0) // If not precomputed, recompute.
        return d[start][end];
    if(start == end) { // The mid character should be taken as 
        d[start][end] = 1;
        return 1;
    }
    else if(start == end-1) {
        d[start][end] = (a[start] == a[end])?2:1;
        return d[start][end];
    }
    if(a[start] == a[end]) {
        d[start][end] = max( 2 + computeMaxPalindromeLength(a, start+1, end-1), 
            max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1)));
    } else {
        d[start][end] = max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1));
    }
    return d[start][end];
}

将上述方法称为：-

vector<int>& a; // Convert each character of string to digit if working with alphanumeric characters.
int maxPalindromeLength = computeMaxPalindromeLength(a, 0, a.size()-1);