python - 最长回文子序列

Question

可能重复：
如何找到最长的回文子序列？

最长回文子序列。
回文是一些字母表上的非空字符串，向前和向后读取相同。回文的例子是所有长度为 1 的字符串、civic、racecar 和 aibohphobia（对回文的恐惧）。给出一个有效的算法来找到给定输入字符串的子序列的最长回文。例如，给定输入“字符”，您的算法应该返回“caac”。

现在，我知道如何获得结果的长度。我怎样才能得到结果的顺序？

def mylongest(self, i, j):
    if j - i <= 1:
        return j-i
    else:
        if self.sequence[i] == self.sequence[j]:
            return self.mylongest(i+1,j-1) + 2
        else:
            return max (self.mylongest(i+1, j), self.mylongest(i, j-1))

Answer 1

使用itertools.combinations()：

In [2]: from itertools import combinations

In [7]: strs="character"

In [8]: for y in range(len(strs)-1,1,-1):
   ...:     for x in combinations(strs,y):
   ...:         if ''.join(x)==''.join(x)[::-1]:
   ...:             print ''.join(x)
   ...:             break
   ...:             
   ...:             
carac
caac
chc
cc