java - 从字符串形成回文

Question

我正在解决字符串中的最长回文问题，我们正在搜索形成回文的最长子字符串。我的上述代码是:

private static int palindrome(char[] ch, int i, int j) {
    // TODO Auto-generated method stub
    if (i == j)
        return 1;

    // Base Case 2: If there are only 2 characters and both are same
    if (ch[i] == ch[j] && i + 1 == j)
        return 2;

    // If the first and last characters match
    if (ch[i] == ch[j])
        return palindrome(ch, i + 1, j - 1) + 2;

    // If the first and last characters do not match
    return max(palindrome(ch, i, j - 1), palindrome(ch, i + 1, j));

}

现在，我很想知道，如果我们不寻找最长的子字符串，而是从字符串中选择随机字符(每个字符仅一个实例)，但顺序与 String 中的顺序相同，则创建一个回文。是否可以在多项式时间内完成此操作？

Answer 1

这个问题可以通过应用 Longest Common Subsequence algorithm (LCS) 来解决。 LCS基本上解决了以下问题:

Given two strings a and b, what is the longest string c that is a subsequence of both a and b?

字符串的子序列是该字符串中按顺序排列的字符序列，其中允许跳过。

现在让我们看看您的问题。 我们想要找到回文字符串 x 的最长子序列。 但是，根据定义，回文是一个向前和向后读取相同的字符串。 因此，同一个回文也将是x的镜像的子序列。

让我们用字符串abca来说明。 显然，它的两个最长的回文子序列是aba和aca。 abca 的镜像是acba。 它的最长回文子序列是什么？还有aba和aca!

所以我们现在可以使用 LCS 来解决您的问题，如下所示:

String longestPalindromicSubsequence(String x) {
    // Get the mirror image of x
    String y = mirror(x);
    return LCS(x,y);
}

LCS 可以在 O(n^2) 时间内完成，其中 n 是字符串的长度。 反转字符串需要线性时间，因此最终运行时间为O(n^2)。