从字符串形成回文

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).

从字符串形成回文

Forming Palindrome from a String

java

string

algorithm

palindrome