最長迴文序列

可能重複：
how to find longest palindromic subsequence?最長迴文序列

最長的迴文序列。
一個palinadrome是對一些字母，讀取相同的向前和向後爲非空字符串。迴文的實例是長度爲1，公民，賽車，和aibohphobia（恐懼迴文）的所有字符串。給出一個efficent算法來找到一個給定的輸入字符串的子序列最長的迴文。例如，給定輸入「字符」，你的算法應該返回「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))

來源

2012-09-14 xiaoke

算法這是這裏討論：http://stackoverflow.com/questions/4790522/how-to-find-longest-palindromic-subsequence – ernie

是這樣的功課從這裏？ www.cs.usfca.edu/~galles/cs673/hw7.btreedp.pdf？ – ernie

實際上，'carac'比'caac'更長 – stark

使用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

來源

2012-09-14 19:19:48

要檢查所有的2^n種組合，我希望這不是最有效的算法......這絕對是效率最低的算法。 – zmbq

我認爲，我們可以使用動態程序被O解決這個問題（N^2）。 – xiaoke

最長迴文序列

回答

相關問題