가장 긴 회문의 서브

Question

가능한 중복 :
how to find longest palindromic subsequence?

가장 긴 회문의 서브.
palinadrome은 전진 및 후진을 읽는 알파벳에 비해 비어 있지 않은 문자열입니다. palindromes의 예는 길이 1, 시민, racecar 및 aibohphobia (palindromes의 공포)의 모든 문자열입니다. 주어진 입력 문자열의 하위 시퀀스 인 최장 palindrome을 찾는 효율적인 알고리즘을 제공하십시오. 예를 들어, 입력 "문자"주어진 알고리즘 "caac"반환해야합니다.

이제는 결과의 길이를 얻는 방법을 알고 있습니다. 어떻게 결과의 순서를 얻을 수 있습니까? itertools.combinations() 사용

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

이위한

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