1

重複の可能性:
最長のパリンドローム部分配列を見つける方法は?

最長回文サブシーケンス。
回文とは、前後に同じように読める、あるアルファベットの空でない文字列です。回文の例としては、長さ 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))
4

1 に答える 1

3

使用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-14T19:19:48.690 に答える