通过删除字符从现有字符串创建回文
如何通过删除零个或多个字母来确定从单词中获得的最长回文的长度。
例如：amanQQQapl12345anacaZZZnalpaXXXna67890ma
最长的回文将是21位数。
这可以通过动态编程来解决。 将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]）。
单词W中最长的回文是W及其镜像的最长公共子序列 。
您可以在O（n²）时间和O（n）空间中计算它，其中n是W的长度但是如果您知道只需要删除几个字符来制作回文，则可以获得更好的复杂性。
一个palidrome最多可以有一个奇数计数的字母，即中间字母，以及任意数量的偶数计数字母。
您可以计算每个字母的频率。 如果每个字母都不是全部或全部，则为每个字母添加count / 2 * 2，如果任何字母具有奇数，则添加一个。
这是@Rambo对答案的正确实施，以防其他人发现他的答案过于简洁。 我已经添加了先前结果的缓存，但条件是不同符号的最大数量最多为1000.由于多个分支使用相同的子分支，这提供了显着的加速。
int d[1000][1000] = {0}; // To store result of previous computation int computeMaxPalindromeLength(vector& 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& a; // Convert each character of string to digit if working with alphanumeric characters. int maxPalindromeLength = computeMaxPalindromeLength(a, 0, a.size()-1);